P1489 猫狗大战

Link

Solution:

f[i][j]= 1 if i cats can make up j blood.

f[0][0]=1

#include <bits/stdc++.h>
# define LL long long
using namespace std;

int n;
int a[210];
int f[210][8010];

int main(){
    scanf("%d", &n);
    int sum=0;
    for(int i=1;i<=n;++i){
        scanf("%d", a+i);
        sum+=a[i];
    }
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=8000;j>=a[i];--j){
            for(int k=i;k>=1;--k){
                if(f[k-1][j-a[i]]==1){
                    f[k][j]=1;
                }
            }
        }
    }
    int ans1=sum;
    int ans2=0;
    int dif=sum;
    for(int i=sum;i>=0;--i){
        if(f[n/2][i]==1){
            if(abs(i-sum+i)<dif){
                dif=abs(i-sum+i);
                ans1=i;
                ans2=sum-i;
            }
        }
    }
    if(ans1>ans2) swap(ans1,ans2);
    printf("%d %d", ans1, ans2);
    return 0;
}