首页 > 搜索 > DFS搜索 > HDU 1516 String Distance and Transform Process-动态规划-[解题报告] C++
2013
12-12

HDU 1516 String Distance and Transform Process-动态规划-[解题报告] C++

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[i][j+1]=dp_temp[i][j]+val[i];
		 dp_temp[i][j+k]=max(dp_temp[i][j+k],dp_temp[i][j]+dp[son[i]][k]);
		
解释一下 dp_temp[i][j]+dp[son[i]][k],其中 son[i]代表i这个节点的孩子节点,
		 假设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];
int head[N],NE;
bool h[N];
void init(){
	NE=0;
	memset(head,-1,sizeof(head));
	memset(dp,-1,sizeof(dp));
	memset(h,0,sizeof(h));
}
void insert(int u,int v){
	E[NE]=node(head[u],v);
	head[u]=NE++;
}
void dfs(int u){
	h[u]=1;
	dp[u][0]=0;
	for(int i=1;i<=m;i++)
		dp[u][i]=val[u];
	for(int i=head[u];i!=-1;i=E[i].next){
		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]);
	}
}

解题报告转自:http://blog.csdn.net/me4546/article/details/6612253