加载中…HDU 3828 A + B problem Multi-University_Training_Contest HNU
(2011-07-13 11:07:26)
标签：
hdu3828abproblemdpit |
分类： 动态规划 |
题目描述：
题意就不讲了，最终的模型是：给你n个长度64的串，让你找一个最短的串str，让这个n个串都是str的子串，如果长度相同，取字典序最小的。
解题报告：
首先，预处理，share[i][j]表示第i个字符串的尾部和第j个字符串的头部的公共长度，如果j是i的子串，直接删除j。
我们从右往左构造字符串（应为比较字典序是从往右的，所以当有答案冲突时，只需要比较最左端的字符串即可得到字典序最小的答案）。
dp[i][j]表示当前在i状态时，用j串作为最左端的串时的最小长度。
i是一个15位二进制数字，哪一位为1表示那一位对应的字符串已经使用过了。
那么，从dp[i][j]开始，一次扫描n个串：
对于串k，如果(i>>k&1) == 0,表示还没用过k，那么可以转移到dp[(i | (1 << k))][k]
转移后的最小长度为：dp[i][j] + len[k] - share[k][j];（减去公共的部分）
这样，每个dp[i][j]都维持一个最小的数字，最后扫描dp[1 << n - 1][x]中的最小值即可。
对于冲突，要维护一个pre[i][j]，表示dp[i][j]是由哪个状态转化过来的。如果在dp[i][j]，冲突，由于是从右往左拼接，那么只需比较冲突的两个串的最头的两个的字典序（比较绕，应该能明白）。
代码如下：
next[i] = j;
int i =
1, j = 1, len1 = strlen(str + 1), len2 = strlen(str2 + 1);
while(i
<= len1 && j
<= len2)
{
if (j == 0 || str[i] ==
str2[j])
{
i++;
j++;
}
else j = next[j];
}
if (j
> len2) return -1;
if (i
> len1) return j - 1;
return
0;
if
(from == -1) strcpy(strtmp, str[j] + 1);
else
strcat(strtmp, str[j] + 1 + share[from][j]);
if
(pre[i][j][0] != -1 && pre[i][j][1]
!= -1)
getans(pre[i][j][0],
pre[i][j][1], j);
long
long ans = 1, jeo = 0;
for(int i = strlen(strtmp2) -
1; i >= 0; i--)
{
if (strtmp2[i] == '1')
{
jeo +=
ans;
if (jeo
>= 1000000009LL) jeo %= 1000000009LL;
}
ans *= 2;
if (ans >= 1000000009LL) ans %=
1000000009LL;
}
return
jeo;
ca =
1;
while(scanf("%d", &n) !=
EOF)
{
for(int i = 0; i
< n; i++)
{
unsigned long long a;scanf("%I64d",
&a);
char tmp[100], ccnt = 0;
while(a)
{
if (a
& 1LL) tmp[ccnt++] = '1';
else
tmp[ccnt++] = '0';
a
>>= 1LL;
}
for(int j = 0, k = ccnt - 1; j <
ccnt; j++, k--)
str[i][j +
1] = tmp[k];
str[i][1 + ccnt] = '\0';
}
memset(share, 0,
sizeof(share));
memset(vst, 0,
sizeof(vst));
for(int i = 0; i
< n; i++)
for(int j = 0; j < n; j++)
{
jeo(str[i]);
if (i != j
&& !vst[j]
&& kmp(str[j], str[i]) == -1)
{
vst[i] = 1;
break;
}
}
int cnt = 0;
for(int i = 0; i
< n; i++)
if (!vst[i]) strcpy(str[cnt++] + 1, str[i] +
1);
n = cnt;
for(int i = 0; i
< n; i++)
{
len[i] = strlen(str[i] + 1);
for(int j = 0; j < n; j++)
{
jeo(str[j]);
share[i][j]
= kmp(str[i], str[j]);
}
}
for(int i = 0; i
< n; i++)
for(int j = 0; j < n; j++)
{
strcpy(cat[i][j], str[i] + 1);
strcat(cat[i][j], str[j] + 1 +
share[i][j]);
}
memset(dp, -1,
sizeof(dp));
memset(pre, -1,
sizeof(pre));
for(int i = 0; i
< n; i++)
{
dp[1 << i][i] =
len[i];
pre[1 << i][i][0] =
-1;
}
for(int i = 1; i
< (1 << n); i++)
for(int j = 0; j < n; j++)
if
(dp[i][j] != -1)
for(int k = 0; k
< n; k++)
if
(!(i>>k&1))
{
int st = (i
| (1 << k));
int val =
dp[i][j] + len[k] - share[k][j];
if
(dp[st][k] == -1 || val < dp[st][k])
{
dp[st][k] = val;
pre[st][k][0] = i;
pre[st][k][1] = j;
}else if
(val == dp[st][k])
{
if (strcmp(cat[k][j],
cat[k][pre[st][k][1]]) < 0)
{
pre[st][k][0] = i;
pre[st][k][1] = j;
}
}
}
int id = -1, mmax =
100000;
for(int i = 0, k = (1
<< n) - 1; i < n;
i++)
{
if (dp[k][i] < mmax)
{
mmax =
dp[k][i];
id =
i;
}else if (dp[k][i] == mmax
&& strcmp(str[i] + 1, str[id] + 1)
< 0)
id =
i;
}
getans((1
<< n) - 1, id, -1);
printf("%I64d\n",
getInt(strtmp));
}
return
0;
题意就不讲了，最终的模型是：给你n个长度64的串，让你找一个最短的串str，让这个n个串都是str的子串，如果长度相同，取字典序最小的。
解题报告：
首先，预处理，share[i][j]表示第i个字符串的尾部和第j个字符串的头部的公共长度，如果j是i的子串，直接删除j。
我们从右往左构造字符串（应为比较字典序是从往右的，所以当有答案冲突时，只需要比较最左端的字符串即可得到字典序最小的答案）。
dp[i][j]表示当前在i状态时，用j串作为最左端的串时的最小长度。
i是一个15位二进制数字，哪一位为1表示那一位对应的字符串已经使用过了。
那么，从dp[i][j]开始，一次扫描n个串：
对于串k，如果(i>>k&1) == 0,表示还没用过k，那么可以转移到dp[(i | (1 << k))][k]
转移后的最小长度为：dp[i][j] + len[k] - share[k][j];（减去公共的部分）
这样，每个dp[i][j]都维持一个最小的数字，最后扫描dp[1 << n - 1][x]中的最小值即可。
对于冲突，要维护一个pre[i][j]，表示dp[i][j]是由哪个状态转化过来的。如果在dp[i][j]，冲突，由于是从右往左拼接，那么只需比较冲突的两个串的最头的两个的字典序（比较绕，应该能明白）。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int next[2000];
void jeo(char str[])
{
int i = 1, len = strlen(str + 1);
next[1] = 0;
int j = 0;
while(i <= len)
{
if (j == 0 || str[i] == str[j])
{
i++;
j++;
}
else
j = next[j];
}
}
//-1 include 0 no x len
int kmp(char str[], char str2[])
{
}
int n, ca;
char str[20][100];
int share[20][20], len[20];
int dp[85536][20];
int pre[85536][20][2];
char strtmp[2000], strtmp2[2000];
void getans(int i, int j, int from)
{
}
long long getInt(char strtmp2[])
{
}
bool vst[20];
char cat[20][20][300];
int main()
{
}
喜欢
0
赠金笔