题解 P1156 【垃圾陷阱】

zhegexiankabutaileng · 2017-03-19 22:16:21 · 题解

贴个非满分题解？？

看到大家都是DP来写的，思路都已经很棒了。

我突发奇想想写个搜索（傻子脸）

由于这题数据太弱，特判一下搜索的层数，超过7ffff层就停止搜索输出目前搜到的答案，如果没有就输出最大存活时间

可以拿90分，90ms过，如果真的是比赛题，这个成绩还是很可观的。。。。。。。

#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
//#include<unordered_map>
using namespace std;
int st=0;
int st2=0;
struct fs
{
    int t;
    int f;
    int h;
}dust[1001];
int comp(fs a,fs b)
{
    return a.t<b.t;
}
//int t[1001]={0},f[1001]={0},h[1001]={0};
int escape=0;
int yg=0x7fffff;
//map<int,int> num;
int d=0,g=0;
int fld=0;
void dfs(int dep,int id,int lv)
{
    if(fld>0x7ffff) 
    {
        if(escape==1)
        {
            cout<<yg;
            exit(0);
        }
        cout<<st+10;;
        exit(0);
    }
    fld++;
    int ht=dep;
    for(int i=id;i<=g;i++)
    {
        int lim=dust[i].t;
        if(lim>lv) return;
        st2=max(st2,lv+dust[i].f);
        dfs(ht,i+1,lv+dust[i].f);
        ht+=dust[i].h;
        if(ht>=d)
        {
            escape=1;
            yg=min(yg,lim);
        }
    }
}
int main()
{
    cin>>d>>g;
    for(int i=1;i<=g;i++)
    {
        //cin>>t[i]>>f[i]>>h[i];
        cin>>dust[i].t>>dust[i].f>>dust[i].h;
        st+=dust[i].f;
        //num[i]=t[i];
    }
    sort(dust+1,dust+1+g,comp);
//    for(int i=1;i<=g;i++)
//    {
//        cout<<dust[i].t;
//    }
    dfs(0,1,10);
    if(escape==1)
    {
        cout<<yg;    
    }
    else
    {
        cout<<st2;
    }

}