2013
12-12

# String Distance and Transform Process

String Distance is a non-negative integer that measures the distance between two strings. Here we give the definition. A transform list is a list of string, where each string, except for the last one, can be changed to the string followed by adding a character, deleting a character or replacing a character. The length of a transform list is the count of strings minus 1 (that is the count of operations to transform these two strings). The distance between two strings is the length of a transform list from one string to the other with the minimal length. You are to write a program to calculate the distance between two strings and give the corresponding transform list.

Input consists a sequence of string pairs, each string pair consists two lines, each string occupies one line. The length of each string will be no more than 80.

For each string pair, you should give an integer to indicate the distance between them at the first line, and give a sequence of command to transform string 1 to string 2. Each command is a line lead by command count, then the command. A command must be

Insert pos,value
Delete pos
Replace pos,value

where pos is the position of the string and pos should be between 1 and the current length of the string (in Insert command, pos can be 1 greater than the length), and value is a character. Actually many command lists can satisfy the request, but only one of them is required.

abcac
bcd
aaa
aabaaaa

3
1 Delete 1
2 Replace 3,d
3 Delete 4
4
1 Insert 1,a
2 Insert 2,a
3 Insert 3,b
4 Insert 7,a

http://acm.hdu.edu.cn/showproblem.php?pid=1561

#include<iostream>
#include<vector>
using namespace std;
#define N 201
vector<int> E[N];
int dp_temp[N][N],dp[N][N];
int val[N],n,m;
bool h[N];

void init(int n){
val[0]=0;
for(int i=0;i<=n;i++)
E[i].clear();
memset(h,0,sizeof(h));
memset(dp,-1,sizeof(dp));
memset(dp_temp,-1,sizeof(dp_temp));
}

void dfs(int u){
if(h[u]) return;
h[u]=1;
dp_temp[u][0]=0;
for(int i=0;i<E[u].size();i++){
int v=E[u][i];
if(!h[v])
dfs(v); //叶子节点未访问过则继续访问
for(int j=m;j>=0;j--)
for(int k=1;k+j<=m;k++)
if(dp_temp[u][j]!=-1&&dp[v][k]!=-1){
if(dp_temp[u][j+k]<dp_temp[u][j]+dp[v][k])
dp_temp[u][j+k]=dp_temp[u][j]+dp[v][k];
}
}
for(int i=0;i<=m;i++)
if(dp_temp[u][i]!=-1)
dp[u][i+1]=dp_temp[u][i]+val[u];
}
int main(void){
while(scanf("%d%d",&n,&m),n||m){
init(n);
for(int i=1;i<=n;i++){
int u;
scanf("%d%d",&u,&val[i]);
E[u].push_back(i);
}
dfs(0);
printf("%d\n",dp[0][m+1]);
}
}

/*

dp[i][j]代表以i为根节点，一共选取j个节点所取得的最大价值，i这个节点一定要选
dp_temp[i][j]代表以i为根节点，一共选取j个节点所取得的最大价值，i这个节点一定不选

dp_temp[i][j+k]=max(dp_temp[i][j+k],dp_temp[i][j]+dp[son[i]][k]);

假设son[i]这个节点中存在选取K个节点这个状态，那么这个孩子节点就
可以向dp_temp[i][j+k]转移，因为转移的时候都是从孩子转移过来的，
那么要是选择了son[i]这个节点，这个节点本身是一定要选择的，
所以转移方程不是 + dp_temp[son[i]][k],而是 +dp[son[i]][k]

*/

#include<iostream>
using namespace std;
#define N 201
int val[N];
int dp[N][N];
int n,m;
struct node{
int next,v;
node(){};
node(int a,int b){
next=a;v=b;
}
}E[N];
bool h[N];
void init(){
NE=0;
memset(dp,-1,sizeof(dp));
memset(h,0,sizeof(h));
}
void insert(int u,int v){
}
void dfs(int u){
h[u]=1;
dp[u][0]=0;
for(int i=1;i<=m;i++)
dp[u][i]=val[u];
int v=E[i].v;
if(!h[v])
dfs(v);
for(int j=m;j>=1;j--)
for(int k=1;k+j<=m;k++){
if(dp[v][k]!=-1)
dp[u][j+k]=max(dp[u][j+k],dp[u][j]+dp[v][k]);
}
}
}
int main(void){
while(scanf("%d%d",&n,&m),n||m){
init();
for(int i=1;i<=n;i++){
int u;
scanf("%d%d",&u,&val[i]);
insert(u,i);
}
m++;
dfs(0);
printf("%d\n",dp[0][m]);
}
}