【hdubestcoder33】

2015.03.18 20:41 Wed | 3次阅读 | 旧日oi | 固定链接 | 源码

把前三个题做了,第一个弱智,第二个递推,第三个挺有意思的,贴个代码留着

我的程序

#include <iostream>
#include <cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 35
using namespace std;
struct Question{
    int t,v,l;
    bool operator<(const Question& q) const{
        return l-t<q.l-q.t;
    }
}q[maxn];
ll re[maxn];
int n,w;
bool dfs(int now,int t,ll val)
{
    if(val>=w) return 1;
    if(now<0) return 0;
    if(val+re[now]<w) return 0;
    if(t>=q[now].l&&t>=q[now].t)
    if(dfs(now-1,t-q[now].t,val+q[now].v)) return 1;
    if(dfs(now-1,t,val)) return 1;
    return 0;
}
int main()
{
    while(cin>>n>>w)
    {
        ll sum=0;
        for(int i=0;i<n;i++) scanf("%d %d %d",&q[i].t,&q[i].v,&q[i].l);
        sort(q,q+n);
        for(int i=0;i<n;i++)
        {
            if(i==0) re[i]=q[i].v;
            else re[i]=re[i-1]+q[i].v;
        }
        if(re[n-1]<w)
        {
            puts("zhx is naive!");
            continue;
        }
        int ans=inf;
        int l=0,r=100000*n;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(dfs(n-1,mid,0))
            {
                r=mid-1;
                ans=mid;
            }
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}```