U218941 题解

一、分析题目

有些饭非常多，可以看作可以一直吃，有些饭很少，只能吃一次。

请你帮助他求出他最多可以吃多少饭，并输出此时所需时间。

从题目我们可以看出，本题为混合背包；

贪心最多90pts；

那么，对于每一顿饭

若能吃无数次，则有：

for(int w = a[i].t;w<=t;w++){  //t为时间
    dp[w]=max(dp[w],dp[w-a[i].t]+a[i].c);  //完全背包
}

若只能吃一次，则有：

for(int w = t;w>=a[i].t;w--){  //t为时间
    dp[w]=max(dp[w],dp[w-a[i].t]+a[i].c);  //01背包
}

二、数据范围

保证0<=ti ;

无穷大符号是”+&

所以 当ti==0时，输出+&；

if(a[i].t==0&&a[i].c){
    cout<<"+&"<<endl;
    return 0;
}

三、$AC$ $Code$

#include<iostream>
using namespace std;
long long dp[1000010];
struct supur{
    int t,c,flag;
}a[1000001];
int main(){
    int n,t;
    cin>>n>>t;
    for(int i = 1;i<=n;i++){
        cin>>a[i].t>>a[i].c>>a[i].flag;
        if(a[i].t==0&&a[i].c){cout<<"+&"<<endl;return 0;}
    }
    for(int i = 1;i<=n;i++){
        if(a[i].flag==0){
            for(int w = a[i].t;w<=t;w++){
                dp[w]=max(dp[w],dp[w-a[i].t]+a[i].c);
            }
        }else{
            for(int w = t;w>=a[i].t;w--){
               dp[w]=max(dp[w],dp[w-a[i].t]+a[i].c);
            }
        }
    }
    cout<<dp[t];
    return 0;
}