当前位置:网站首页>P1278 单词游戏(状压dp)

P1278 单词游戏(状压dp)

2021-08-10 07:00:03 wx6110fa547fd20

P1278 单词游戏(状压dp)

状压dp的裸题,令 d p [ i ] [ j ] dp[i][j] dp[i][j]表示状态 i i i以单词 j j j结尾的最大长度。

然后转移即可。

时间复杂度: O ( 2 n n 2 ) O(2^nn^2) O(2nn2)

void solve(){
	IOS;cin>>n;for(int i=0;i<n;i++){
		cin>>a[i];
		f[1<<i][i]=SZ(a[i]);
	}
	int st=1<<n;
	for(int i=0;i<st;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++){
				if(j!=k&&a[j][SZ(a[j])-1]==a[k][0]&&(i>>j&1)&&!(i>>k&1))
					f[i|1<<k][k]=max(f[i|1<<k][k],f[i][j]+SZ(a[k]));
			}
	int ans=0;
	for(int i=0;i<st;i++)
		for(int j=0;j<n;j++) ans=max(ans,f[i][j]);
	cout<<ans<<'\n';
	//think twice code once
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328228