北京赛区,又输给软件咯。

zzz哥状态不太好,我们也不给力,开始一个多小时后我们才进入状态,唉。

共享一个题目,Tourism Planning。其他的,不说了。

半枚举,半DP,用了位运算优化。本来应该可以1Y的,但是交的时候选错了语言,而且程序结束条件没注意,一个CE,一个WA,今天真够人品的。

思路,先求出人组合的所有情况(2^N)的那个景点的价值,存在vl矩阵里面,然后一个个景点遍历,如果上一个状态能够转移过来的,取所有能够转移的最大值就可以了。

#include <cstdio>
#include <cstring>
#define inf 99999999

int n,m;
int ct[11];
int it[11][11];
int aw[11][11];
int qw[1100];
int vl[11][1100];

int main(){
	int i,j,k,l,max;
	while(~scanf("%d%d",&n,&m)){
		if(n==0&&m==0)break;
		for(i=0;i<m;i++)
			scanf("%d",&ct[i]);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++){
				scanf("%d",&it[i][j]);
				it[i][j]-=ct[j];
			}
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				scanf("%d",&aw[i][j]);
		memset(qw,0,sizeof(qw));
		for(i=0;i<(1<<n);i++){
			for(j=0;(1<<j)<=i;j++){
				if(!((1<<j)&i))continue;
				for(k=j+1;(1<<k)<=i;k++){
					if(!((1<<k)&i))continue;
					qw[i]+=aw[j][k];
				}
			}
		}
		for(i=0;i<m;i++){
			for(j=0;j<(1<<n);j++){
				vl[i][j]=qw[j];
				for(k=0;k<n;k++){
					if((1<<k)&j)
						vl[i][j]+=it[k][i];
				}
			}
		}
		for(i=1;i<m;i++){
			for(j=0;j<(1<<n);j++){
				max=-inf;
				for(k=0;k<(1<<n);k++){
					if((j&k)==j){
						if(max<vl[i-1][k])max=vl[i-1][k];
					}
				}
				if(max!=-inf){
					vl[i][j]+=max;
				}
			}
		}
		max=0;
		for(i=0;i<(1<<n);i++){
			if(max<vl[m-1][i])max=vl[m-1][i];
		}
		if(max==0){
			printf("STAY HOMEn");
		}else{
			printf("%dn",max);
		}
	}
	return 0;
}