dp(武功秘籍）

众所周知，太吾绘卷是非常爱（niu）你（bi）的国产武侠游戏，里面有一个继承系统，当你死后可以在你的子孙中挑选一个继承人，用他的人物继续进行游戏。当你挑选继承人的时候一定会挑选能力最强，天赋最高的那一个来继承。这样你培养的时候也会重点培养天赋最高的那一个。某zf大侠有两个继承人，第一个天赋很高，第二个天赋比较平庸，zf大侠想重点培养第一个继承人，但是又怕第二继承人觉得不公平，所以他会在尽量公平的基础上来重点培养第一个继承人。Zf大侠有n种秘籍，每种秘籍都能提升某个人一定的能力，请你帮zf大侠决定怎么培养继承人吧。Input本题有多组输入，每组数据第一行输入由整数N（0 < N <= 50）组成，表示秘籍的种类。接下来N行，每行两个整数V（0 当N为负数时程序结束。Output每组数据输出一行，包含两个数字A和B，分别带表两个继承人最终获得的能力大小（一开始两个继承人的能力都为0），A和B用空格分开。Sample Input

Sample Output

20 10

40 40

解析：dp[sum/2]是其全部的一半（能取到的话）或者为其最小的那一分

#include<bits/stdc++.h>

using namespace std;

const int maxn=5e5+;

int dp[];

int a[];

int main()

{

    int n;

    while(~scanf("%d",&n)&&n>=){

        memset(a,,sizeof(a));

        memset(dp,,sizeof(dp));

        int x,y,sum=;

        int cnt=;

        for(int i=;i<=n;i++){

            scanf("%d%d",&x,&y);

            sum+=x*y;

            int t=;

            while(y>=t){

                a[cnt]=x*t;

                cnt++;

                y-=t;

                t*=;

            }

            if(y>){

                a[cnt]=x*y;

            }

        }

        int v=sum/;

        for(int i=;i<=cnt;i++){

            for(int j=v;j>=a[i];j--){

                dp[j]=max(dp[j],dp[j-a[i]]+a[i]);

            }

        }

        printf("%d %d\n",sum-dp[v],dp[v]);

    }

    return ;

}

巴特西

dp(武功秘籍）

最新文章

热门文章