新疆大学ACM-ICPC程序设计竞赛五月月赛(同步赛)J Most Powerful

题目链接https://www.nowcoder.com/acm/contest/116/J

题意:略。

思路:考虑状压DP0表示当前位还没消失,1表示当前位已经经过碰撞后消失,设dp[status]为当前状态获得的最大分数,然后我们枚举当前状态里已经消失的和没有消失的位置ij,转移即为dp[status]=max(a[i][j]+dp[status-2^j]),时间复杂度O(n^2*2^n)

#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
int n,i,j,res,status,a[15][15],dp[1500];
int main(){
    while (~scanf("%d",&n)&&n){
        for (res=0,i=0;i<n;i++) for (j=0;j<n;j++) read(a[i][j]);
        memset(dp,0,sizeof(dp));
        int lim=1<<n;
        for (status=1;status<lim;status++){
            for (i=0;i<n;i++)if(status&(1<<i)){
                for (j=0;j<n;j++)if(!(status&(1<<j))){
                    dp[status]=max(dp[status],dp[status^(1<<i)]+a[j][i]);
                }
            }
        }
        for (i=0;i<n;i++) res=max(res,dp[lim-1-(1<<i)]);
        printf("%d\n",res);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注