UESTC1565 Smart Typist
Time Limit: 2000 ms Memory Limit: 65536 kB Solved: 10 Tried: 49
Description
The most mysterious organization in Chani is “Related Department”. It is related to almost everything, and has branches almost everywhere. Events always have relation with it. Whenever disasters happen, “Related Department” would stand out to commit its responsibility. The members of “Related Department” are called “Related person”. However, ordinary people have no idea about who is “Related person” since their information is national secret.
Xiaoming is the top typist in Chani. The legend is that he could type 400 words per minute. Today he accepted an order from a man who said that he is a “Related person”. That “Related person” asked Xiaoming to turn many paper documents into electronic files. For reasons of security, Xiaoming has to use a special device which has limited functions. With the special device, Xiaoming can only perform such operations:
1. Creating a new file. It takes a quite short time that we ignore the time for it.
2. Replacing current file with some file finished before. A file is allowed to be used to replace another one only after it is finished and won’t be edited later.
3. Deleting any letter(s) in current file.
4. Inserting letter(s) at arbitrary position in current file.
Note that, the keyboard for this device is so strange that the time for typing different letter may be different.
Xiaoming is somewhat afraid of dealing with “Related person”, so he wants to accomplish this order as soon as possible. Knowing time needed for each operation, Xiaoming is trying to make the best plan which spends the minimum time.
Input
The first line of the input is T (no more than 50), which stands for the number of test cases you need to solve.
Each case begins with two integers, repCost and delCost (1 <= repCost, delCost <= 50), time needed to replace current file, time for deleting one letter. On the second line, there are 26 numbers representing the time for typing each letter from ‘a’ to ‘z’, each number is between 1 and 50.
Then a line with an integer N (1 <= N <= 50) is given indicating the number of files.
N lines followed. Each line gives a string only consisting of letters ‘a’-‘z’ to represent a file. The maximum length of the strings is not greater than 50.
Output
For every test case, you should output "Case #k: c" first in a line, where k indicates the case number and counts from 1, c is the minimum time needed.
Simple Input
2
1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aaab
aaaa
10 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aaab
aaaa
Simple Output
Case #1: 7
Case #2: 8
**************************************************************
题目大意：某个打字员要打n个字符串，有如下操作：
1.创建一个一个文件，不计时间。
2.用一个已经存在的文件替换当前文件，花费为rep
3.删除某些字符，每删除一个字符的花费为del
4.在当前文件任意位置增加字符，花费为val[字符]。
求打完这些字符串所要的最小花费。
解题思路：这道题，怎么说呢。我们把每个字符串当一个节点，一个字符串到另一个字符串的变化花费计算出来，然后再有一个最终节点连到所有的字符串，权值为打这个字符串的花费。那么，问题转化为这个有向图中的最小树形图。建图很简单，求最小树形图也不过是套用朱刘算法的模板，然而令人纠结的是怎么把一个字符串变化到另一个字符串的花费，要不是这个，我也不会写这道题。这个花费很难算啊，经过我、YYB、ZYC一个晚上的思考，终于相处了这个dp过程，真是艰辛苦楚。
直接考虑s1变化到s2的dp：
dp[0][1~len1]=del*len1代表全部删除，以后一个一个匹配进来。
dp[i][0]=dp[i-1][0]+val[i];
dp[i][j],当s1的第i个==s2的第j个字母，dp[i][j]=dp[i-1][j-1]-del;当s1的第i个!=s2的第j个字母,dp[i][j]=min(dp[i][j-1],dp[i-1][j]+val[i]);
dp很难想 真心的。
//#pragma comment(linker, "/STACK:65536000")
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <fstream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define N 55
#define M 30
#define E
#define inf 0x3f3f3f3f
#define dinf 1e10
#define linf (LL)1<<60
#define eps 1e-8
#define LL long long
#define clr(a,b) memset(a,b,sizeof(a))
#define D(a) ((a)*(a))
using namespace std;
int n;
int del,rep,val[M],gra[N][N];
string s[N];
int dp[N][N];
int pre[N],vis[N],cnt,ced[N];//ced数组用来缩点用的
void dpt(int a,int b)
{
string s1=s[a],s2=s[b];
int len1=s1.size(),len2=s2.size();
for(int i=0;i<=len1;i++)dp[0][i]=len1*del;
for(int i=1;i<=len2;i++)
{
dp[i][0]=dp[i-1][0]+val[s2[i-1]-'a'];
for(int j=1;j<=len1;j++)
if(s1[j-1]==s2[i-1])
dp[i][j]=dp[i-1][j-1]-del;
else
dp[i][j]=min(dp[i][j-1],dp[i-1][j]+val[s2[i-1]-'a']);
}
gra[a][b]=dp[len2][len1]+rep;
}
void dfs(int s)//dfs判是否有解
{
vis[s]=1;cnt++;
for(int i=1;i<=n;i++)
if(gra[s][i]<dinf&&!vis[i])
dfs(i);
}
int ZHULIU(void)
{
clr(ced,0);int ans=0;
int i,j,k;
do
{
for(i=2;i<=n;i++)//清除自环，以及求每个点的入边
{
if(ced[i])continue;
pre[i]=1;
for(j=2;j<=n;j++)
if(j!=i&&!ced[j]&&gra[pre[i]][i]>gra[j][i])
pre[i]=j;
}
for(i=2;i<=n;i++)
{
if(ced[i])continue;
clr(vis,0);
for(j=i;j!=1&&!vis[j];j=pre[j])vis[j]=1;//寻找环，被vis标记的是环内的点
if(j==1)continue;
ans+=gra[pre[j]][j];
for(i=pre[j];i!=j;i=pre[i])//把环里的权值加到ans中去
ans+=gra[pre[i]][i],ced[i]=1;
for(k=1;k<=n;k++)//这个和下面那个for在缩点
if(!ced[k]&&gra[k][j]<inf)
gra[k][j]-=gra[pre[j]][j];
for(i=pre[j];i!=j;i=pre[i])
for(k=1;k<=n;k++)
{
if(ced[k])continue;
gra[j][k]=min(gra[j][k],gra[i][k]);
if(gra[k][i]<inf)
gra[k][j]=min(gra[k][j],gra[k][i]-gra[pre[i]][i]);
}
break;
}
}while(i<=n);
for(int i=2;i<=n;i++)//把不是剩下的入边都加上
if(!ced[i])ans+=gra[pre[i]][i];
return ans;
}
void re(void)
{
cin>>rep>>del;
for(int i=0;i<26;i++)cin>>val[i];
cin>>n;n++;
for(int i=2;i<=n;i++)
cin>>s[i];
}
void run(void)
{
for(int i=2;i<=n;i++)
for(int j=2;j<=n;j++)
gra[i][j]=inf;
for(int i=2;i<=n;i++)
for(int j=2;j<=n;j++)
if(i!=j)
dpt(i,j);
for(int i=2;i<=n;i++)
{
int a=0,len=s[i].size();
for(int j=0;j<len;j++)a+=val[s[i][j]-'a'];
gra[1][i]=a;
}
cout<<ZHULIU()<<endl;
}
int main()
{
//freopen("d:\\in.txt","r",stdin);
int ncase;
scanf("%d",&ncase);
for(int i=1;i<=ncase;i++)
{
re();
cout<<"Case #"<<i<<": ";
run();
}
return 0;
}