背景
2009NOIP余姚中学内部暑期集训
7月14号模拟赛第三题
描述
Cpg 正在游览一个梦中之城，在这个城市中有n棵摇钱树。。。这下，可让Cpg看傻了。。。可是Cpg只能在这个城市中呆K天，但是现在摇钱树已经成熟了，每天每棵都会掉下不同的金币。Cpg每天可以砍掉其中一颗，并获得其树上说有的金币（怎么会有这种好事。。。）。请你帮助Cpg算出他在这K天中最多能获得多少金币。
格式
输入格式
每个文件中有不超过10组测试数据。
每组测试数据：
第一行两个整数n，K (1<=K<=n<=1000)
第二行n个整数Mi (Mi <= 100000).表示Cpg刚看到这n棵树时每刻树上的金币数。
第三行n个整数 Bi.(Bi<=1000)表示每颗摇钱树，每天将会掉落的金币。
以n=K=0结束。
输出格式
对每组测试数据，输出仅一行，Cpg在K天中能获得的最大金币数。
样例1
样例输入1
3 3
10 20 30
4 5 6
4 3
20 30 40 50
2 7 6 5
0 0样例输出1
47
104限制
各个测试点1s
提示
样例1的解释:第一天摘第三个果子得到30,第二天摘第二个果子得到15,第三天摘第一个果子得到2,30+15+2=47
首先orz出题人。好题。
这道题我们对于发现他的最优子结构还是很容易的。
f[k][S]表示前k天用了S的子集的最优解，
转移f[k][S]=f[k-1][p];(p属于S).
我们观察一下它有没有贪心属性，很显然没有，你必须知道前面的装态。
但我们可以容易的发现如果取了其中几个，一定是减少快的在前面取。
我们不妨先排个序。
发现，我们不用需要S了，只要一个j表示前k天用了前j棵树。
不需要顺序了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<cstdlib> 7 #include<vector> 8 using namespace std; 9 typedef long long ll; 10 typedef long double ld; 11 typedef pair<int,int> pr; 12 const double pi=acos(-1); 13 #define rep(i,a,n) for(int i=a;i<=n;i++) 14 #define per(i,n,a) for(int i=n;i>=a;i--) 15 #define Rep(i,u) for(int i=head[u];i;i=Next[i]) 16 #define clr(a) memset(a,0,sizeof(a)) 17 #define pb push_back 18 #define mp make_pair 19 #define fi first 20 #define sc second 21 #define pq priority_queue 22 #define pqb priority_queue <int, vector<int>, less<int> > 23 #define pqs priority_queue <int, vector<int>, greater<int> > 24 #define vec vector 25 ld eps=1e-9; 26 ll pp=1000000007; 27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} 28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} 29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } 30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; } 31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1}; 32 ll read(){ ll ans=0; char last=' ',ch=getchar(); 33 while(ch<'0' || ch>'9')last=ch,ch=getchar(); 34 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); 35 if(last=='-')ans=-ans; return ans; 36 } 37 #define N 1005 38 struct node{ 39 int a,b; 40 }f[N]; 41 bool cmp(node a,node b){ 42 return a.b>b.b; 43 } 44 int dp[N][N]; 45 int main(){ 46 while (1){ 47 int n=read(),k=read(); 48 if (n==0 && k==0) break; 49 for (int i=1;i<=n;i++) f[i].a=read(); 50 for (int i=1;i<=n;i++) f[i].b=read(); 51 sort(f+1,f+n+1,cmp); 52 memset(dp,0,sizeof(dp)); 53 for (int i=1;i<=k;i++){ 54 for (int j=1;j<=n;j++) 55 dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+f[j].a-(i-1)*f[j].b); 56 } 57 int ans=0; 58 for (int i=1;i<=k;i++) ans=max(ans,dp[i][n]); 59 printf("%d ",ans); 60 } 61 }