HDU 3578 Greedy Tino(双塔DP)
2024-09-29 02:19:13
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.
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.
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;
}
最新文章
- 前端应当了解的Web缓存知识
- 【转】Linq Group by
- [Django 2]第一个django应用
- layzr.js新版使用方法
- Mysql数据库操作系统及配置参数优化
- [Android Tips] 2. Disable recent apps dialog on long press home button
- [OpenCV] Face Detection
- sizeWithFont方法被弃用了,该怎么办?
- FZU 2016 summer train I. Approximating a Constant Range 单调队列
- php面向对象设计模式
- hdu 5676 ztr loves lucky numbers(dfs+离线)
- centos 7 linux 安装与卸载 tomcat 7
- 8.异常_EJ
- VP-UML系统建模工具研究
- [转]mysql和redis的区别
- MFC 使用用指定USB设备串口
- Qt 添加 QtNetwork 库文件
- 【Ruby】【YAML】
- ipv6下jdbc的连接数据库方式
- sql 2014 安装失败
热门文章
- 解决nginx到后端服务器Connection: close问题
- idea lib下有jar包但是仍然报错 找不到类
- Unity中差乘判断目标是否在左边或右边
- [svc][op]如何查看当前Ubuntu系统的版本
- CodeForces 579b
- MySQL 行号(类似SQLServer的row_number())
- MVVM 实战之计算器
- cocos2dx错误收集
- 数据库设计(三)11 important database designing rules which I follow
- Unity3D避免代码被反编译