虽然转移方程可以一眼看出
但是烦就烦在为何要排序
有人说这是一个贪心，又有人说这是一个保障正确性的。
就按照贪心的想法好了：在保证正确性的情况下尽量多的挂钩。
#include<bits/stdc++.h> #define N 2005 #define INF 0x3f3f3f3f using namespace std; int n,f[N][N]; struct Node { int a,b; }node[N]; inline bool cmp(const Node &x,const Node &y) { return x.a>y.a; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=1;i<=n;i++) cin>>node[i].a>>node[i].b; sort(node+1,node+n+1,cmp); for(int i=0;i<=n;i++) f[0][i]=-INF,f[i][n+1]=-INF; f[0][1]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=n;j++) { f[i][j]=max(f[i-1][j],f[i-1][max(j-node[i].a,0)+1]+node[i].b); } } int ans=0; for(int i=0;i<=n;i++) ans=max(ans,f[n][i]); cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9911926.html
