http://poj.org/problem?id=2817?

?

這個題的意思是第一行給出case數N (1 <= N <= 10)，然后給出N個單詞，每個一行，當輸入不是正整數的時候結束。每個單詞最多10個字母。
Sample Input
5
abc
bcd
cde
aaa
bfcde
0
要求的是，按任意順序排列這些單詞，可以在單詞前面加任意個空格，使得相鄰的單詞上下對應的字母數目最多，并輸出最多是多少。
Sample Output
8
比如sample里面的8，是這樣得來的：
aaa
abc
?bcd
? cde
bfcde
注意只有相鄰單詞的字母上下對應才算對應。

?

/*
由于每兩個串的最大相同 字符數 是一定的，所以 這個我們是要考慮一個排列使 ，公共字符最多


狀態壓縮 ， dp[i][j]? 表示 在 狀態 i 時 以? 串 j 結尾的 最大 個數
dp[i][j] = max(dp[k][x]) (x 是沒有 被選的 ，k ==? i &(~(1<<x)))


*/

?

??1?#include<cstdio>
??2?#include<cstring>
??3?#include<cmath>
??4?#include<iostream>
??5?#include<algorithm>
??6?#include<set>
??7?#include<map>
??8?#include<queue>
??9?#include<vector>
?10?#include<string>
?11?#define?Min(a,b)?a<b?a:b
?12?#define?Max(a,b)?a>b?a:b
?13?#define?CL(a,num)?memset(a,num,sizeof(a));
?14?#define?maxn??520
?15?#define?eps??1e-8
?16?#define?inf?100000000
?17?
?18?#define?ll???__int64
?19?using?namespace?std;
?20?int?len[12];
?21?char?word[12][12]?;
?22?int?dp[1500][12]?;
?23?int?n;
?24?int?com[12][12]?;
?25?int??cal(int?a,int?b)//計算最大?公共字符數
?26?{
?27?????int?i,j;
?28?????int?mx?=?0;
?29?????int?sum?;
?30?????for(i?=?0?;?i??<?len[a];i++)
?31?????{
?32???????????sum?=?0;
?33?????????for(j?=?0;j?+?i?<?len[a]?&&?j?<?len[b]?;j++)
?34?????????{
?35?
?36?????????????if(word[a][i?+?j]?==?word[b][j])?sum?++;
?37?
?38?
?39?????????}
?40?????????if(sum?>?mx)?mx?=?sum?;
?41?????}
?42?????for(i?=?0;i<?len[b];i++)
?43?????{
?44?????????sum?=?0;
?45?????????for(j?=?0?;?j?+?i<?len[b]?&&?j<?len[a];j++)
?46?????????{
?47?????????????if(word[b][i?+?j]?==?word[a][j])sum?++;
?48?
?49?????????}
?50?????????if(sum?>?mx)?mx?=?sum?;
?51?????}
?52?????return?mx?;
?53?}
?54?int?get(int?stat?,int?k)
?55?{
?56?????int??i;
?57?????if(stat?==?0)??return?0;
?58?????if(dp[stat][k])?return?dp[stat][k];
?59?
?60?????stat?&=?(~(1<<k))?;
?61?????int?mx?=?0?,d;
?62?????for(i?=?0?;i?<?n;i++)
?63?????{????int?tmp?=?stat&(~(1<<i))?;
?64??????????if(tmp?!=?stat)
?65??????????{
?66??????????????d?=?get(?tmp?,i)?+?com[i][k]?;
?67??????????????if(d?>?mx)?mx?=?d;
?68?????????}
?69?
?70?
?71?????}
?72??????dp[stat][k]?=?mx?;
?73?
?74?????return???dp[stat][k]?;
?75?}
?76?int?main()
?77?{
?78?????int?i,j;
?79?????while(scanf("%d",&n),n>0)
?80?????{
?81?????????CL(dp,0);
?82?????????for(i?=?0;?i?<?n;i++)
?83?????????{
?84?????????????scanf("%s",word[i]);
?85?????????????len[i]?=?strlen(word[i]);
?86?????????}
?87?????????for(i?=?0;?i?<n?;i++)
?88?????????{
?89?????????????for(j?=?i+1;j<n;j++)
?90?????????????{
?91?????????????????com[i][j]?=?com[j][i]?=?cal(i,j);
?92?
?93?????????????}
?94?
?95?????????}
?96?
?97?????????/*for(i?=?0;?i?<?n;i++)
?98?????????{
?99?????????????for(j?=?0?;?j<?n;j++)
100???????????????printf("%d?",com[i][j]);
101?
102?????????????printf("\n");
103?????????}*/
104?
105?????????int?stat?=?(1<<n)?-?1;
106?
107?????????int?ans?=?0,tmp;
108?????????for(i?=?0?;?i?<?n;i++)
109?????????{
110?????????????tmp?=?get(stat,i);
111?????????????if(tmp?>?ans)ans?=?tmp?;
112?????????}
113?????????printf("%d\n",ans);
114?????}
115?}

?

?

轉載于:https://www.cnblogs.com/acSzz/archive/2012/08/22/2651243.html

總結

以上是生活随笔為你收集整理的poj 2817 WordStack （状态dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。