PAT刷题记录12.11
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;
}
美团成长空间 2663人发布
