cl少用在for循环里
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 typedef long long ll; 13 #define cl(a) memset(a,0,sizeof(a)) 14 #define ts printf("***** "); 15 const int MAXN=15; 16 int n,m,tt; 17 int dp[15][1<<12],cost[MAXN],in[MAXN][MAXN],a[MAXN][MAXN],st[MAXN]; 18 int main() 19 { 20 int i,j,k,ca=1; 21 #ifndef ONLINE_JUDGE 22 freopen("1.in","r",stdin); 23 #endif 24 while(scanf("%d%d",&n,&m)!=EOF&&n&&m) 25 { 26 for(i=1;i<=m;i++)scanf("%d",cost+i); 27 for(i=1;i<=n;i++) 28 for(j=1;j<=m;j++) scanf("%d",&in[i][j]); 29 for(i=1;i<=n;i++) //陪同 30 { 31 for(j=1;j<=n;j++) scanf("%d",&a[i][j]); 32 } 33 //dp初始化 34 for(i=1;i<=m;i++) 35 { 36 for(j=0;j<=(1<<n)-1;j++) dp[i][j]=-10000000; 37 } 38 for(i=0;i<=(1<<n)-1;i++) dp[0][i]=0; 39 for(i=1;i<=m;i++) 40 for(j=0;j<=(1<<n)-1;j++) 41 { 42 int tot=0; 43 //当前状态取得的值 44 int temp=j; 45 for(k=1;k<=n;k++) 46 { 47 st[k]=temp%2; 48 if(st[k]) tot+=(in[k][i]-cost[i]); 49 temp/=2; 50 } 51 //printf("%d ",tot); 52 //陪伴加成 53 for(k=1;k<=n;k++) 54 { 55 for(int kk=k+1;kk<=n;kk++) 56 { 57 if(st[k]&&st[kk]) 58 { 59 tot+=a[k][kk]; 60 } 61 } 62 } 63 //之前的转态 64 int ans=1; //状态总和 65 int pre[1<<12]; 66 pre[0]=j; 67 for(k=1;k<=n;k++) 68 { 69 if(!st[k]) //该人当前未出现，则之前可能是出现也可能是没出现 70 { 71 int sum=ans; 72 for(int kk=0;kk<ans;kk++) 73 { 74 int nst=pre[kk]^(1<<(k-1)); 75 pre[sum++]=nst; 76 } 77 ans=sum; 78 } 79 } 80 //加上之前的转态 81 int Max=-10000000; 82 for(k=0;k<ans;k++) 83 { 84 if(Max<dp[i-1][pre[k]]) 85 { 86 Max=dp[i-1][pre[k]]; 87 } 88 } 89 dp[i][j]=Max+tot; 90 } 91 int Max=-10000000; 92 for(i=1;i<=m;i++) 93 { 94 for(j=0;j<=(1<<n)-1;j++) 95 { 96 if(Max<dp[i][j]) Max=dp[i][j]; 97 } 98 } 99 if(Max<=0) printf("STAY HOME "); 100 else printf("%d ",Max); 101 } 102 }