【ZOJ - 3211】Dream City （01背包类问题，贪心背包）

题干：

JAVAMAN is visiting Dream City and he sees a yard of gold coin trees. There are n trees in the yard. Let's call them tree 1, tree 2 ...and tree n. At the first day, each tree i has ai coins on it (i=1, 2, 3...n). Surprisingly, each tree i can grow bi new coins each day if it is not cut down. From the first day, JAVAMAN can choose to cut down one tree each day to get all the coins on it. Since he can stay in the Dream City for at most m days, he can cut down at most m trees in all and if he decides not to cut one day, he cannot cut any trees later. (In other words, he can only cut down trees for consecutive mor less days from the first day!)

Given n, m, ai and bi (i=1, 2, 3...n), calculate the maximum number of gold coins JAVAMAN can get.

Input

There are multiple test cases. The first line of input contains an integer T (T <= 200) indicates the number of test cases. Then T test cases follow.

Each test case contains 3 lines: The first line of each test case contains 2 positive integers n and m (0 < m <= n <= 250) separated by a space. The second line of each test case contains n positive integers separated by a space, indicating ai. (0 < ai <= 100, i=1, 2, 3...n) The third line of each test case also contains n positive integers separated by a space, indicating bi. (0 < bi <= 100, i=1, 2, 3...n)

Output

For each test case, output the result in a single line.

Sample Input

Sample Output

10
21

Hint

s:
Test case 1: JAVAMAN just cut tree 1 to get 10 gold coins at the first day.
Test case 2: JAVAMAN cut tree 1 at the first day and tree 2 at the second day to get 8 + 10 + 3 = 21 gold coins in all.

解题报告：

本来思考：定义的状态是：dp[i][j] 第i天砍了第j棵树，但是这个肯定不对，以为看不到之前哪些砍过哪些没砍。dp[i][j]代表第i填砍了前j棵树，你i天肯定砍了i棵树，那么剩下的肯定都从后面砍的，所以涉及到一个排序问题，而且这个状态定义会有后效性，所以pass掉。

正解：dp[i][j]代表考虑对于第i棵树，总共砍了j棵树（或者砍了j天），的最大价值，那么此时有选和不选两种状态，分别转移。问题转化成：也就是我有一个体积为m的背包，n个物品，每个物品体积为1，并且物品的价值随放入顺序而改变，问你最优放入顺序（最大价值）。

那么这种问题肯定要贪心排序，处理掉“物品的价值会随时间改变而改变” 这一要素，对于这题假设我们选了m种物品，那么肯定b越大的越后选。所以我们按照b排序。这样就是n个物品选m个物品的最优解问题了，01背包解决。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 500 + 5;

int n,m;
set<int> ss[MAX][MAX];
ll val[MAX][MAX];//第i棵树 第j天  的val 
struct Node {
	int a,b;
	bool operator<(const Node c)const{
		return b < c.b;
	}
} node[MAX];
ll dp[MAX];
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d",&n,&m);
		memset(dp,-0x3f,sizeof dp);
		for(int i = 1; i<=n; i++) scanf("%d",&node[i].a);
		for(int i = 1; i<=n; i++) scanf("%d",&node[i].b);
		memset(val,0,sizeof val);
		sort(node+1,node+n+1);
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=m; j++) {
				if(j == 1) val[i][j] = node[i].a;
				else val[i][j] = val[i][j-1] + node[i].b;
			}
		}
		dp[0]=0;
		for(int i = 1; i<=n; i++) {
			for(int j = m; j>=1; j--) {
				dp[j] = max(dp[j],dp[j-1] + val[i][j]);
			}
		}
		printf("%lld\n",dp[m]);
	}


	return 0 ;
}