poj 2288

題意:ハミルトニアンループを求めますが、重みの計算は3つの部分を含みます:1はすべての点の重みの加算を経ます.2経過した連続する2つの点の重みの積.3は、三角型の連続3点の積を構成することができる.これらをすべて合わせると、この回路の総重み値になります.最大ウェイト値とこの最大ウェイト値を出力するルートは何本ありますか.
この問題は今までで最も私の卵を痛めた問題で、すべて問題の解を見て書いたのですが、まだ不思議なものが現れていません.昨夜からずっとwaで、私はずっと間違いを探していましたが、ずっと結果が出ていません.今日は思い切って新しく書きましたが、1 yになりました.昨夜の間違いを見つけるために、私は絶えず区分して処理して、最後にdpの過程で確定して、それから一つ一つ実験をコピーしました.しかし、私は彼らの2つのコードをタッチするように変更して、10+回調べて、違いはありませんが、まだ1つのwa、1つのacです.私はこのコードをdiscussに入れて、後の人が解読するのを待っています.
この問題は明らかなdpですが状態設定は、ちょっと考えにくいですが、せいぜい3つの点に関係しているので、3つの状態を設定しました.dp[s][i][j]は、s状態で最後にi点に到達し、前の到達点式j点の最大値を表す.dp[s][i][j]=tem;tem=isv[i]+isv[i]*isv[j]+dp[ss][j][k]+gp[i][k]?isv[i]*isv[j]*isv[k]:0;temはijのみがつながっており,三角形にならない場合と,三角形を形成する場合に分けられる.パス数はこの最大値に移行できればそのまま加算すればよい.
Run ID
User
Problem
Result
Memory
Time
Language
Code Length
Submit Time
9215970
201030720425
2288
Accepted
50484K
1079MS
C++
1884B
2011-08-23 11:30:58
コード#コード#

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
long long dp[1<<14][14][14],isv[14],isl[1<<14][14][14];
bool gp[14][14];
int n,m;
void DP()
{
	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;
			int tem=(1<<i)+(1<<j);
			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][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 tem=(1<<n)-1;
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
				{
					if(i==j) continue;
					if(ans<dp[tem][i][j])
					{
						ans=dp[tem][i][j];
						count=isl[tem][i][j];
					}
					else if(ans==dp[tem][i][j])
						count+=isl[tem][i][j];
				}
				if(ans==-1)
					printf("0 0
");
				else
					printf("%lld %lld
",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
",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;
}