首页 > 其他 > 详细

zoj3471 状态压缩dp基础

时间:2019-02-09 23:37:54      阅读:243      评论:0      收藏:0      [点我收藏+]
/*
dp[S]表示状态S下的最大收益,0表示没有了,1表示还在 
*/
#include<bits/stdc++.h>
using namespace std;
int dp[1<<11],mp[11][11],n;
int main(){
    while(cin>>n && n){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)cin>>mp[i][j];
        memset(dp,0,sizeof dp);
        int ans=0;
        
        for(int S=(1<<n)-1;S>=1;S--)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)//消去i留下j 
                    if( (S&(1<<(i-1))) && (S&(1<<(j-1))) && i!=j )
                        dp[S-(1<<(i-1))]=max(dp[S-(1<<(i-1))],dp[S]+mp[j][i]),ans=max(ans,dp[S-(1<<(i-1))]); 
        printf("%d\n",ans);            
    }
} 

 

zoj3471 状态压缩dp基础

原文:https://www.cnblogs.com/zsben991126/p/10358473.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!