Top Level 1002 Business (35分)
分析 :PAT总是不给数据范围很讨厌,这题用map装dp保险(虽然并不用开ll,pat审题人有点毒瘤),还是第一次遇到。表示考虑到第 i 个物品,走到的天数为 j 。
code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;
struct Node {
    int d,len,v;
    bool operator < (const Node &T) const {
        return d<T.d;
    }
}pp[maxn];
map<int,map<int,int> > dp;
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&pp[i].v,&pp[i].len,&pp[i].d);
    sort(pp+1,pp+1+n);
    for(int i=1;i<=n;i++) for(int j=0;j<=pp[i-1].d&&j+pp[i].len<=pp[i].d;j++) for(int k=0;k<i;k++)
    {
        dp[i][j+pp[i].len]=max(dp[i][j+pp[i].len],dp[k][j]+pp[i].v);
        ans=max(ans,dp[i][j+pp[i].len]);
    }
    printf("%d",ans);
    return 0;
}