ZOJ 3211 Dream City(线性DP)
Dream City
Time Limit: 1 Second Memory Limit: 32768 KB
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 aicoins 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 m or 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
Hints:
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.
Author: CAO, Peng
Source: The 6th Zhejiang Provincial Collegiate Programming Contest
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
int s,grow;
}a[];
int t,n,m;
int dp[][];
bool cmp(node a,node b)
{
return a.grow<b.grow;
} int main()
{
while(~scanf("%d",&t))
{
for(;t>;t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i].s);
for(int i=;i<=n;i++)
scanf("%d",&a[i].grow);
sort(a+,a+n+,cmp);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)//dp[i][j]表示到第i棵树为止,砍了j棵获得的最多金币
for(int j=;j<=m;j++)
dp[i][j]=max(dp[i][j],max(dp[i-][j],dp[i-][j-]+a[i].s+(j-)*a[i].grow)); printf("%d\n",dp[n][m]);
}
}
return ;
}
最新文章
- objective-c 宏定义UIAlertController公用方法
- JAVA中的字符串小结
- SQLServer子查询
- 了解 MVC 应用程序执行过程
- Trie的C++实现及HDU1251,hdu1671
- win8笔记本无法搜索wifi信号找不到WLAN该 wifi共享特别注意的服务
- 好用的JQ图片特效jquery-poptrox-popup-galleries
- xtrabackup 链接不上MySQL的问题
- 查看htmlView
- LeetCode: Distinct Subsequences [115]
- (转载)#include机制,#ifndef...#define...#endif防止重复引用,声明,定义等概念
- HDU2544-最短路(最短路模版题目)
- Linux环境下配置JDK,java环境
- Think with Google 京东如何玩转TensorFlow?
- mysql_config not found和error: command &#39;gcc&#39; failed with exit status 1
- mysql数据表增删改查
- Data type
- .net core实践系列之短信服务-Sikiro.SMS.Bus服务的实现
- using 自动释放资源示例
- 修改nose_html_reporting,解决输出带中文时,不能生成html文件