sicily 1221 背包

//背包 给n个数，从中取m个数，每个数有下降速度 //首先想到如果已经知道这m个数是谁，那就直接下降速度快的先取就可以了，所以要先排序 //这里只要m个数，典型的0-1背包 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; int n,m; int dp[201]; struct Node { int s,d; }node[201]; bool operator < ( Node a,Node b ) { return a.d > b.d; } inline int mx( int a,int b) { return a > b ? a : b; } int main() { scanf("%d",&n); scanf("%d",&m); for( int i = 0;i < n;i++ ) scanf("%d",&node[i].s); for( int i = 0;i < n;i++ ) scanf("%d",&node[i].d); sort( node,node+n ); for( int i = 0;i < n;i++ ) { for(int j = m;j >= 1;j-- ) { dp[j] = mx( dp[j],dp[j-1] + node[i].s-node[i].d * (j-1) ); } } cout<<dp[m]<<endl; }