有一种想死的感觉，两段代码检查了10+遍，毫无差别，但是换成下面注释里面的就A，不换就WA。谁能够解释这一神奇的现象？

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
int gp[14][14];
long long dp[1<<14][14][14],isv[14],isl[1<<14][14][14];
void DP()
{
	long long tem;
	memset(dp,-1,sizeof(dp));
	memset(isl,0,sizeof(isl));
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			{
				if(i==j||gp[i][j]==0)continue;
			    tem=(1<<j)+(1<<i);
				dp[tem][i][j]=isv[i]+isv[j]+isv[i]*isv[j];
				isl[tem][i][j]=1;
			}			
			for(int s=0;s<(1<<n);s++)
				for(int i=0;i<n;i++)
				{
					if((s&(1<<i))==0)continue;
					for(int j=0;j<n;j++)
					{
						if(i==j||(s&(1<<j))==0||gp[i][j]==0)continue;
						for(int k=0;k<n;k++)
						{
							if(k==j||k==i||(s&(1<<k))==0||gp[j][k]==0)continue;
							int ss=s-(1<<i);
							if(dp[ss][j][k]==-1)continue;
					        long long tem=isv[i]+isv[i]*isv[j]+dp[ss][j][k];
							if(gp[i][k]) tem+=isv[i]*isv[j]*isv[k];
							if(tem>dp[s][j][j])
							{
								dp[s][i][j]=tem;
								isl[s][i][j]=isl[ss][j][k];
							}
							else
							    if(tem==dp[s][j][j])
								    isl[s][i][j]+=isl[ss][j][k];
						}
					}
				}
		/*		
		for(int s=0;s<(1<<n);s++)
			for(int i=0;i<n;i++)
			{
				if((s&(1<<i))==0)continue;
				for(int j=0;j<n;j++)
				{
					if(i==j||(s&(1<<j))==0||gp[i][j]==0)continue;
					for(int k=0;k<n;k++)
					{
						if(k==j||k==i||(s&(1<<k))==0||gp[j][k]==0)continue;
						int ss=s-(1<<i);
						if(dp[ss][j][k] ==-1)continue;
					    long long tem=isv[i]+isv[i]*isv[j]+dp[ss][j][k];
						if(gp[i][k]) tem+=isv[i]*isv[j]*isv[k];
						if(tem>dp[s][i][j])
						{
							dp[s][i][j]=tem;
							isl[s][i][j]=isl[ss][j][k];
						}
						else
							if(tem==dp[s][i][j])
								isl[s][i][j]+=isl[ss][j][k];
					}
				}
			}*/
				long long ans=-1,count=0;
				int ss=(1<<n)-1;
					for(int i=0;i<n;i++)
						for(int j=0;j<n;j++)
						{
							if(i==j)
								continue;
							if(ans<dp[ss][i][j])
							{
								ans=dp[ss][i][j];
								count=isl[ss][i][j];
							}
							else if(dp[ss][i][j]==ans)
								count+=isl[ss][i][j];
						}
						if(ans==-1)
							printf("0 0\n");
						else
							printf("%lld %lld\n",ans,count/2);

}
int main()
{
    int c,x,y;
	scanf("%d",&c);
	while(c--)
	{
		memset(gp,0,sizeof(gp));
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++)
			scanf("%lld",&isv[i]);
		if(n==1)
		{
			printf("%lld 1\n",isv[0]);
			continue;
		}
		for(int i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
			gp[x-1][y-1]=gp[y-1][x-1]=1;
		}
		DP();
	}
	return 0;
}

• acm十大未解之谜 已解 (38) gripleaf 2011-08-23 18:18:11
  • Re:acm十大未解之谜 已解 (42) 201030720425 2011-08-25 12:56:50
  • Re:acm十大未解之谜 已解 (58) 201030720425 2011-08-25 12:57:18