題干：

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

2 2 1 10 10 1 1 2 2 8 10 2 3

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.

解題報(bào)告：

本來(lái)思考：定義的狀態(tài)是：dp[i][j] 第i天砍了第j棵樹(shù)，但是這個(gè)肯定不對(duì)，以為看不到之前哪些砍過(guò)哪些沒(méi)砍。dp[i][j]代表第i填砍了前j棵樹(shù)，你i天肯定砍了i棵樹(shù)，那么剩下的肯定都從后面砍的，所以涉及到一個(gè)排序問(wèn)題，而且這個(gè)狀態(tài)定義會(huì)有后效性，所以pass掉。

正解：dp[i][j]代表考慮對(duì)于第i棵樹(shù)，總共砍了j棵樹(shù)（或者砍了j天），的最大價(jià)值，那么此時(shí)有選和不選兩種狀態(tài)，分別轉(zhuǎn)移。問(wèn)題轉(zhuǎn)化成：也就是我有一個(gè)體積為m的背包，n個(gè)物品，每個(gè)物品體積為1，并且物品的價(jià)值隨放入順序而改變，問(wèn)你最優(yōu)放入順序（最大價(jià)值）。

那么這種問(wèn)題肯定要貪心排序，處理掉“物品的價(jià)值會(huì)隨時(shí)間改變而改變” 這一要素，對(duì)于這題假設(shè)我們選了m種物品，那么肯定b越大的越后選。所以我們按照b排序。這樣就是n個(gè)物品選m個(gè)物品的最優(yōu)解問(wèn)題了，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棵樹(shù) 第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 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【ZOJ - 3211】Dream City （01背包类问题，贪心背包）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。