题意:
给出N个串, 将其排列在N行上, 利用空格缩进, 使得每一行和上面一行的串重叠的部分最长. 求这个长度.
思路:
N最大为10, 考虑状压dp.
state为串的状态, dp[state][ i ] 表示state状态下以第 i 个串开头的方案中,重叠的最大长度. 则有:
枚举state中的任意一个串 i 作为第一行, 另一个串 j 作为第二行, state' = state^(1<<i);(去掉第 i 个串)
dp[state][ i ] = dp[state' ][ j ] + cat[ i ][ j ] or cat[ j ][ i ];
其中, cat[ i ][ j ]表示 i 和 j 重叠的最大长度...暴力一下
题意"重叠"理解有误了....不一定要连续.....只要对上就行
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 12;
const int INF = 0x3f3f3f3f;
int next[MAXN],dp[1<<10][MAXN],cat[MAXN][MAXN],n;
char str[MAXN][MAXN],dis[MAXN];
//fill cat[i][j]...bruce
int cmp(char a[], int la, char b[], int lb)
{
int ans = 0;
int pa = la - 1, pb = 0;
for(;pa>=0;pa--)
{
int cnt = 0;
for(int i=0;i<la-pa && i<lb-pb;i++)
if(a[pa+i]==b[pb+i]) cnt++;
ans = max(ans, cnt);
}
pa = 0;
for(;pb<lb;pb++)
{
int cnt = 0;
for(int i=0;i<la-pa && i<lb-pb;i++)
if(a[pa+i]==b[pb+i]) cnt++;
ans = max(ans, cnt);
}
return ans;
}
void pre()
{
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
cat[i][j] = cat[j][i] = cmp(str[i],strlen(str[i]),str[j],strlen(str[j]));
}
/*
char* bin(int x)
{
dis[n] = '\0';
for(int i=0;i<n;i++)
{
if((1<<i)&x) dis[n-i-1] = '1';
else dis[n-i-1] = '0';
}
return dis;
}*/
int dfs(int s, int i)
{
if(dp[s][i]!=INF) return dp[s][i];
if(!s) return dp[s][i] = 0;
int cnt = __builtin_popcount(s);
if(cnt==1) return dp[s][i] = 0;
int ans = 0;
for(int j=0;j<n;j++)
if(i!=j && (1<<j)&s)
ans = max(ans, dfs(s^(1<<i),j)+cat[i][j]);
//printf("dp[%s][%d] = %d\n",bin(s^(1<<i)),j,dp[s^(1<<i)][j]);
return dp[s][i] = ans;
}
int main()
{
while(scanf("%d",&n)==1 && n>0)
{
for(int i=0;i<n;i++)
scanf("%s",str[i]);
pre();
int ans = 0;
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<n;i++)
ans = max(ans, dfs((1<<n)-1, i));
// printf("dp[%s][%d] = %d\n",bin((1<<n)-1),i,dp[(1<<n)-1][i]);
printf("%d\n",ans);
}
}
除了题意理解有误之外...
这是很久以来第一次自己想出算法的一题TAT....
看了下题解...有更好的dp方式...不需要dfs...直接填表
就是定义dp[ state ][ i ]为state状态下最后一个选取的串为 i 时, 重叠的最大字符数.
转移的时候并不是去掉(这样的话就又成dfs了)而是加入...
看原文吧:
状态转移:
枚举某个状态时，枚举一个已选的字符串（即当前状态二进制位为1的位），再枚举一个未选的字符串（当前状态二进制位为0的位），通过这两个字符串的拼接来更新拼接之后新的状态，因为加进了一个没在状态中的字符串，所以状态变成了i|(1<<k) 假设i是当前枚举的状态，k是二进制位为0的位
所以状态转移就为
dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+len[j][k]);
如果大家仔细观察一下代码中的关键转移部分，会发现：当我们要去更新dp[i|(1<<k)][k]状态时，dp[i][j]肯定已经是求好了的，在这道题目里dp[i][j]就是dp[i|(1<<k)][k]的子结构，每次都尝试着用dp[i|(1<<k)][k]的子结构去更新它.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 12;
const int INF = 0x3f3f3f3f;
int next[MAXN],dp[1<<10][MAXN],cat[MAXN][MAXN],n;
char str[MAXN][MAXN],dis[MAXN];
//fill cat[i][j]...bruce
int cmp(char a[], int la, char b[], int lb)
{
int ans = 0;
int pa = la - 1, pb = 0;
for(;pa>=0;pa--)
{
int cnt = 0;
for(int i=0;i<la-pa && i<lb-pb;i++)
if(a[pa+i]==b[pb+i]) cnt++;
ans = max(ans, cnt);
}
pa = 0;
for(;pb<lb;pb++)
{
int cnt = 0;
for(int i=0;i<la-pa && i<lb-pb;i++)
if(a[pa+i]==b[pb+i]) cnt++;
ans = max(ans, cnt);
}
return ans;
}
void pre()
{
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
cat[i][j] = cat[j][i] = cmp(str[i],strlen(str[i]),str[j],strlen(str[j]));
}
int solve()
{
memset(dp[0],0,sizeof(dp[0]));
memset(dp[1],0,sizeof(dp[1]));
for(int state=1;state<1<<n;state++)
for(int i=0;i<n;i++)
if((1<<i)&state)
for(int j=0;j<n;j++)
if((1<<j)&(~state))
dp[state|(1<<j)][j] = max(dp[state|(1<<j)][j], dp[state][i]+cat[i][j]);
int ans = 0;
for(int i=0;i<n;i++)
ans = max(ans, dp[(1<<n)-1][i]);
return ans;
}
int main()
{
while(scanf("%d",&n)==1 && n>0)
{
for(int i=0;i<n;i++)
scanf("%s",str[i]);
pre();
int ans = 0;
memset(dp,0,sizeof(dp));
printf("%d\n",solve());
}
}