题目链接：https://acm.ecnu.edu.cn/contest/695/problem/C/
做法
我是状压 DP 做的，不难发现，我们可以把这一行被上一行占用的位置保存下来，然后转移。
显然如果 $x$ 转移到 $y$ ，那么 $x\And y=0$ ，而这是一个经典的 trick ，这样子转移的复杂度是 $O(3^m)$ 的，所以最终时间复杂度就是：$O(n3^m)$ 。
不过看题解说其实有效转移 $<6000$ ？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<bits/stdc++.h>
#define N 310
#define M 160
using namespace std;
struct node{
int a[26],len,fa;
}tr[N];int tot,last;
char st[M];int n;
void add(int c){
int p=last;int np=last=++tot;
tr[np].len=tr[p].len+1;
for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;
if(!p)tr[np].fa=1;
else{
int q=tr[p].a[c];
if(tr[q].len==tr[p].len+1)tr[np].fa=q;
else{
int nq=++tot;
tr[nq].fa=tr[q].fa;tr[q].fa=nq;
tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a));
tr[np].fa=nq;
for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;
}
}
}
bool dp[N][M][M];
int m,X;char ans[M];int fuck;
int getval(int x,int fucklen){
int cnt=1;
for(int i=fucklen;i>=1;i--){
if(tr[x].a[ans[i]-'a'])x=tr[x].a[ans[i]-'a'];
else x=tr[1].a[ans[i]-'a'],cnt++;
}
return cnt;
}
bool v[40];
bool work(){
if(fuck!=m){
for(int i=2;i<=tot;i++){
int x=getval(i,fuck);
if(x<=X && dp[i][m-fuck][X-x+1])return 1;
}
return 0;
}
else return getval(tr[1].a[ans[m]-'a'],m-1)==X;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&X);
scanf("%s",st+1);
tot=last=1;memset(tr,0,sizeof(tr));memset(v,0,sizeof(v));
for(int i=1;i+i<=n;i++)swap(st[i],st[n-i+1]);
for(int i=1;i<=n;i++)add(st[i]-'a'),v[st[i]-'a']=1;
for(int i=0;i<=25;i++){
if(tr[1].a[i])dp[tr[1].a[i]][1][1]=1;
}
for(int i=1;i<m;i++){
for(int j=2;j<=tot;j++){
for(int t=1;t<=i && t<=X;t++){
if(!dp[j][i][t])continue;
for(int k=0;k<=25;k++){
if(tr[j].a[k])dp[tr[j].a[k]][i+1][t]=1;
else if(tr[1].a[k] && t<X)dp[tr[1].a[k]][i+1][t+1]=1;
}
}
}
}
bool bk=0;
for(int i=1;i<=tot;i++)bk|=dp[i][m][X];
if(!bk){
for(int i=1;i<=tot;i++)memset(dp[i],0,sizeof(dp[i]));
printf("-1\n");continue;
}
for(int i=1;i<=m;i++){
fuck=i;
for(int j=0;j<=25;j++){
if(!v[j])continue;
ans[i]=j+'a';
if(work()==1)break;
}
}
ans[m+1]='\0';printf("%s\n",ans+1);
for(int i=1;i<=tot;i++)memset(dp[i],0,sizeof(dp[i]));
}
return 0;
}
|
官方做法：
可以发现 $(i,j)$ 至多从 $(i-1,j-1)$ 转移过来，所以可以直接轮廓线 DP ，保存所有需要位置的状态就行了。
时间复杂度：$O(nm2^m)$ 。
