洛谷1489 猫狗大战

Posted by yjjr's blog on February 6, 2018

标签:DP,动态规划,背包

题目描述

新一年度的猫狗大战通过SC(星际争霸)这款经典的游戏来较量,野猫和飞狗这对冤家为此已经准备好久了,为了使战争更有难度和戏剧性,双方约定只能选择Terran(人族)并且只能造机枪兵。

比赛开始了,很快,野猫已经攒足几队机枪兵,试探性的发动进攻;然而,飞狗的机枪兵个数也已经不少了。野猫和飞狗的兵在飞狗的家门口相遇了,于是,便有一场腥风血雨和阵阵惨叫声。由于是在飞狗的家门口,飞狗的兵补给会很快,野猫看敌不过,决定撤退。这时飞狗的兵力也不足够多,所以没追出来。

由于不允许造医生,机枪兵没办法补血。受伤的兵只好忍了。555-

现在,野猫又攒足了足够的兵力,决定发起第二次进攻。为了使这次进攻给狗狗造成更大的打击,野猫决定把现有的兵分成两部分,从两路进攻。由于有些兵在第一次战斗中受伤了,为了使两部分的兵实力平均些,分的规则是这样的:1)两部分兵的个数最多只能差一个;2)每部分兵的血值总和必须要尽可能接近。现在请你编写一个程序,给定野猫现在有的兵的个数以及每个兵的血格值,求出野猫按上述规则分成两部分后每部分兵的血值总和。

输入输出格式

输入格式:

第一行为一个整数n(1<=n<=200),表示野猫现在有的机枪兵的个数。以下的n行每行一个整数,表示每个机枪兵的血格(1<=ai<=40)。

输出格式:

一行,为两个整数,表示分成两部分后每部分兵的血值总和

输入输出样例

输入样例#1:

3

35

20

32

输出样例#1:

35 52

 

题意:

给定:正整数序列a1……an

求:将这些数分为两部分,个数差值<=1,每部分和差值最小

W1 二进制模拟   n<=20

W2  动态规划:f[i][j][k]表示选了前i个人中j个兵是否可以构成血量为k,之后就转化为一个背包问题的变形,优化一维f[i][j]表示选i个兵能否构成j的血量

状态转移方程 f[i][j]=f[i][j]|f[i-1][j-a[i]]

最后统计答案是从sum(所有的人血量和)除以2开始枚举,发现的第一个满足的方案时就输出解。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=206,maxsum=8006;
int n,sum=0,a[maxn],f[maxn][maxsum];

int main()
{
    scanf("%d",&n);
    f[0][0]=1;
    rep(i,1,n)scanf("%d",&a[i]),sum+=a[i];
    rep(i,1,n)
        dep(j,n/2,1)
            dep(k,sum,a[i])
                f[j][k]|=f[j-1][k-a[i]];
    dep(i,sum/2,0)
        if(f[n/2][i]){printf("%d %d\n",i,sum-i);return 0;}
}
        




本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr