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; }