| 记录编号 |
400022 |
评测结果 |
WAWWWWWWWWWWWWWWWWWW |
| 题目名称 |
[SCOI 2008] 劣质编码 |
最终得分 |
5 |
| 用户昵称 |
 不存在的 |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
0.007 s |
| 提交时间 |
2017-04-28 22:10:59 |
内存使用 |
3.34 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
typedef short BOOL;
const int N = 61;
const int _MAX = 1000000000;
int n,m,len[N];
int ans,dp[N][N][N][3];
char data[N][N];
BOOL cmp[N][N][N];
struct zht{
int a,i,j,t;
zht(){}
zht(int aa,int ii,int jj,int tt):a(aa),i(ii),j(jj),t(tt){}
};
queue<zht> dui;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+'){fh=-1;cc=getchar();}
if(cc=='+'){fh=1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
int scans(char s[]){
char cc=' ';int i;
cc=getchar();
for(i=1;!(cc=='\r'||cc=='\n');i++){
s[i]=cc;
cc=getchar();
}s[i]=0;
return i-1;
}
int main(){
freopen("codez.in","r",stdin);
freopen("codez.out","w",stdout);
int i,j,k;
n=scan();
for(i=1;i<=n;i++){
len[i]=scans(data[i]);
while(data[i][len[i]]==' ')data[i][len[i]--]=0;
if(len[i]==0){printf("0\n");return 0;}
}
//找出所有可以转移的位置
//也就是判断相等
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
for(k=0;k<len[i];k++){
int tmp=min(len[i]-k,len[j]),ii;
for(ii=1;ii<=tmp;ii++)
if(data[i][ii+k]!=data[j][ii]) break;
cmp[i][j][k] = ii>tmp;
}cmp[i][j][len[i]]=1;
}
for(i=0;i<=n;i++)
for(j=0;j<N;j++)
for(k=0;k<N;k++)
dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=_MAX;
for(i=1;i<=n;i++){
dui.push(zht(i,0,0,2));
dp[i][0][0][2]=len[i];
}
ans=_MAX;
while(!dui.empty()){
zht now = dui.front(); dui.pop();
int aa,ii,jj,tt,l;
int &Dp = dp[now.a][now.i][now.j][now.t];
//另外匹配的两个串结构不同
if(!now.t){
//update ans
if(now.i==now.j&&now.i==len[now.a]){
if(dp[now.a][now.i][now.j][now.t]<ans)
ans=dp[now.a][now.i][now.j][now.t];
continue;
}
//枚举新的匹配串
for(i=1;i<=n;i++){
/*
[tt.a]
111111111
1111111
[i]
转移状态
*/
//tt.i > tt.j
//接到匹配位数少的那一个上
if(!cmp[now.a][i][now.j]) continue;tt=0;
//如果接超了，就把新接的串当成tt.a
if(len[i]+now.j > len[now.a]){
//由于等式的传递关系,长的匹配一定可以匹配到新串i上
//并且可以得到之前的串tt.a转换成的匹配一定比j长
aa=i;ii=len[now.a]-now.j;jj=now.i-now.j;
l=Dp + len[i] - (len[now.a]-now.j);
//否则只是更新一下长度
}else{
aa=now.a;ii=now.j+len[i];jj=now.i;
if(jj>ii)swap(jj,ii);
l=Dp;
}
//push
if(l < dp[aa][ii][jj][tt]){
dui.push(zht(aa,ii,jj,tt));
dp[aa][ii][jj][tt]=l;
}
}
//模板串和匹配i串结构相同
}else if(now.t==1){
//因为两个匹配结构相同，故不能更新答案
if(now.i==now.j&&now.i==len[now.a])continue;
//枚举新的匹配串
for(i=1;i<=n;i++){
//接到短的上
if(!cmp[now.a][i][now.j]) continue;
if(now.j+len[i] >= len[now.a]){
//如果接超了，就把新接的串当成tt.a
aa=i;ii=jj=len[now.a]-now.j;tt=2;
l=Dp + len[i] - ii;
}else{
aa=now.a;ii=now.i;jj=now.j+len[i];tt=1;
l=Dp;
}
//push
if(l < dp[aa][ii][jj][tt]){
dui.push(zht(aa,ii,jj,tt));
dp[aa][ii][jj][tt]=l;
}
}
//结构相同的两个匹配串
}else if(now.t==2){
for(i=1;i<=n;i++){
if(!cmp[now.a][i][now.i])continue;
//不要拿自己和自己匹配
if(now.i==0&&i==now.a) continue;
//一下放两个一样的
if(now.j+len[i] > len[now.a]){
aa=i;ii=len[i];jj=len[now.a]-now.j;tt=1;
l=Dp + len[i] - jj;
}else{
aa=now.a;ii=jj=now.i+len[i];tt=2;
l=Dp;
}
//push
if(l < dp[aa][ii][jj][tt]){
dp[aa][ii][jj][tt]=l;
dui.push(zht(aa,ii,jj,tt));
}
//枚举第二个匹配串
for(j=1;j<=n;j++){
//******能接上去********
if(!cmp[now.a][j][now.j]) continue;
//两个新匹配串不能是同一个串 ,但是内容需要相同
if(i==j)continue;
//能接上去
if(!cmp[i][j][0])continue;
int si=i,sj=j;
//若不相等保证 len[si] > len[sj]
//若长度相等且sj==当前串 则使si==当前串
if(len[sj] > len[si] || (len[si]==len[sj]&&sj==now.a)) swap(si,sj);
if(now.i+len[si] > len[now.a]){
if(now.j+len[sj] > len[now.a]){
aa=si;ii=len[sj];jj=len[now.a]-now.i;
l=Dp+ len[si]-jj;
tt=0;
}else{
aa=si;ii=len[now.a]-now.i;jj=len[sj];
l=Dp+len[si]-ii;
//sj和tt.a相同而si较长 仍是2状态
//***我不知道为啥这里一开始填的是 if(ii==jj)
if(now.a==sj&&now.i==0) tt=2;
else tt=0;
}
}else{
aa=now.a;ii=now.i+len[si];jj=now.i+len[sj];tt=0;
l=Dp;
if(now.i==0&&si==now.a){
if(jj<len[now.a])tt=1;
//相等
else{
aa=sj;ii=jj=len[sj];
tt=2;
}
}
}
if(l < dp[aa][ii][jj][tt]){
dp[aa][ii][jj][tt]=l;
dui.push(zht(aa,ii,jj,tt));
}
}
}
}
}
if(ans==_MAX)
printf("-1\n");
else
printf("%d\n",ans);
return 0;
}