首页 > 代码库 > HDU 2291

HDU 2291

2024-07-31 06:36:32   208人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=2291

读题读的烦死了，今天果真不适合做题

题意：给两个n*n的矩阵，第一个代表一个人战胜一个人可以得到的经验值，第二个代表一个人战胜另一个人可以得到的分数，然后n个数，代表n个人的初始经验值，只有经验值大于对手才可以取胜，问第一个人最后取得的最大分数

n只有13，状压dp随便搞一下

#include <iostream>#include <cstdio>#include <cstring>using namespace std ;int dp[1<<15];int e[1005],r[1005],s[15],n;int exp(int x){    int st=1;    int res=s[0];    for(int i=0;i<n-1;i++){        if((x>>i)&1){            res+=e[st];        }        st++;    }    return res;}int main(){    int T;    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=0;i<n*n;i++)            scanf("%d",&e[i]);        for(int i=0;i<n*n;i++)            scanf("%d",&r[i]);        for(int i=0;i<n;i++)            scanf("%d",&s[i]);        memset(dp,0,sizeof(dp));        for(int i=0;i<(1<<(n-1));i++){            for(int j=0;j<n-1;j++){                if(i&(1<<j)){                    if(exp(i^(1<<j))>s[j+1]){                        dp[i]=max(dp[i],dp[i^(1<<j)]+r[j+1]);                    }                }            }        }        printf("%d\n",dp[(1<<(n-1))-1]);    }    return 0;}
View Code

 

HDU 2291


联系
我们