HDU 3578 Greedy Tino(双塔DP)

Greedy Tino

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1194    Accepted Submission(s): 393

Problem Description

  Tino wrote a long long story. BUT! in Chinese...   So I have to tell you the problem directly and discard his long long story. That is tino want to carry some oranges with "Carrying pole", and he must make two side of the Carrying pole are the same weight. Each orange have its' weight. So greedy tino want to know the maximum weight he can carry.

Input

The first line of input contains a number t, which means there are t cases of the test data.   for each test case, the first line contain a number n, indicate the number of oranges.   the second line contains n numbers, Wi, indicate the weight of each orange   n is between 1 and 100, inclusive. Wi is between 0 and 2000, inclusive. the sum of Wi is equal or less than 2000.

Output

For each test case, output the maximum weight in one side of Carrying pole. If you can't carry any orange, output -1. Output format is shown in Sample Output.

Sample Input

1
5
1 2 3 4 5

Sample Output

Case 1: 7
双塔DP注意如果有一个橘子是0,那么就符合条件dp[i][j] 表示第i个橘子,两边差值#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
int n;
int a[105];
int dp[105][4005];
int main()
{
	int t;
	scanf("%d",&t);
	int cas=0;
	while(t--)
	{
		scanf("%d",&n);
		int num=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]==0)
				i--,n--,num++;
			
		}
		memset(dp,-1,sizeof(dp));
		dp[0][0+2000]=0;
		for(int i=1;i<=n;i++)
		{
			memcpy(dp[i],dp[i-1],sizeof(dp[i]));
			for(int j=-2000;j<=2000;j++)
			{
				
                if(dp[i-1][j+2000]==-1) continue;

				if(j<0)
				{
                    dp[i][j-a[i]+2000]=max(dp[i][j-a[i]+2000],dp[i-1][j+2000]+a[i]);
                    dp[i][j+a[i]+2000]=max(dp[i][j+a[i]+2000],dp[i-1][j+2000]+max(0,j+a[i]));
				}
				else
				{
					
					 dp[i][j+a[i]+2000]=max( dp[i][j+a[i]+2000],dp[i-1][j+2000]+a[i]);
                     dp[i][j-a[i]+2000]=max(dp[i][j-a[i]+2000],dp[i-1][j+2000]+max(0,a[i]-j));
				}
			}
		}
		
		if(dp[n][2000])
			printf("Case %d: %d\n",++cas,dp[n][2000]);
		else
		{
			if(num>=1)
				printf("Case %d: %d\n",++cas,0);
			else
			   printf("Case %d: %d\n",++cas,-1);
		}
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 12...

3318
来自专栏ml

HDUOJ------1711Number Sequence

Number Sequence Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/3...

3046
来自专栏ml

HDUOJ---大菲波数

大菲波数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

29911
来自专栏算法修养

HDU 4745 Two Rabbits(区间DP,最长非连续回文子串)

Two Rabbits Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535...

3146
来自专栏算法修养

POJ-1458 Common Subsequence(线性动规,最长公共子序列问题)

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submis...

3287
来自专栏ml

hdu-----(2807)The Shortest Path(矩阵+Floyd)

The Shortest Path Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/...

4215
来自专栏ml

HDUOJ---A + B Again

A + B Again Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 ...

29311
来自专栏算法修养

CodeForces 25C(Floyed 最短路)

F - Roads in Berland Time Limit:2000MS     Memory Limit:262144KB     64bit IO...

2374
来自专栏算法修养

HDU 4597 Play Game(DFS,区间DP)

Play Game Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K ...

3075
来自专栏算法修养

CodeForces Roads not only in Berland(并查集)

H - Roads not only in Berland Time Limit:2000MS     Memory Limit:262144KB    ...

2535

扫码关注云+社区

领取腾讯云代金券