简单dp - Yzhid

Two Kinds of Guessing

Within a subproblem
– Crazy Eights: previous card in trick
– Sequence alignment: align/drop one character
– Bellman‐Ford: previous edge in path
– Floyd‐Warshall: use vertex ?
– Parenthesization: last multiplication
– Knapsack: include item ?
– Tetris training: how to place piece

Using additional subproblems
– Knapsack: how much space left in knapsack
– Tetris training: current board configuration

矩阵取数

http://www.51nod.com/tutorial/course.html#!courseId=1
给定一个m行n列的矩阵，矩阵每个元素是一个正整数，你现在在左上角（第一行第一列），你需要走到右下角（第m行，第n列），每次只能朝右或者下走到相邻的位置，不能走出矩阵。走过的数的总和作为你的得分，求最大的得分。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 500+1
int main(){
//	freopen("yzhid.in", "r", stdin);
   //freopen("yzhid.out", "w", stdout);
	int n,a[MAX][MAX],d[MAX][MAX];

	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	d[0][0]=a[0][0];	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		d[i][j]=max(d[i-1][j],d[i][j-1])+a[i][j];
	}
	printf("%d\n",d[n][n]);	
	return 0;
}

最大字段和问题

http://www.51nod.com/tutorial/course.html#!courseId=2
给出一个整数数组a(正负数都有)，如何找出一个连续子数组（可以一个都不取，那么结果为0），使得其中的和最大？

#define MAX 50000+1 
int main(){
	//freopen("yzhid.in", "r", stdin);
	int n,a[MAX];
	long long endmax,ans;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	endmax=a[1];
	ans=a[1];
	for (int i=2;i<=n;i++){
		endmax=max(endmax,(long long)0)+a[i];
		ans=max(ans,endmax);
	}
	printf("%lld",ans);
	return 0;
}

最长公共子序列

http://www.51nod.com/tutorial/course.html#!courseId=4
给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000+5
char a[MAX],b[MAX],c[MAX];
int dp[MAX][MAX],r[MAX][MAX];
int main(){
	freopen("yzhid.in", "r", stdin);
	scanf("%s\n%s",&a[1],&b[1]);
	int la=strlen(&a[1]),lb=strlen(&b[1]);		
	for(int i=0;i<=la;i++)
		for(int j=0;j<=lb;j++){
			if (i == 0 || j== 0)
	            dp[i][j]= 0;
	        else if (a[i]==b[j]) {
	        	dp[i][j]=dp[i-1][j-1]+1;
	        	r[i][j]=2;
	        }
	        else if(dp[i-1][j]>=dp[i][j-1]){
        		dp[i][j]=dp[i-1][j];
        		r[i][j]=1;
	        }
        	else {
        		dp[i][j]=dp[i][j-1];
        		r[i][j]=3;
        	}
		} 
	char ans[MAX];
	int t=0,i=la,j=lb;
	while(i>0&&j>0){
		if(r[i][j]==2){
			ans[t++]=a[i];
			i--;j--;
		}
		else if(r[i][j]==1){
			i--;
		}
		else if(r[i][j]==3){
			j--;
		}
	}
	for(int i=t-1;i>=0;i--)
		putchar(ans[i]);
	return 0;
}

编辑距离问题

http://www.51nod.com/tutorial/course.html#!courseId=3
给定两个字符串S和T，对于T我们允许三种操作：

(1) 在任意位置添加任意字符
(2) 删除存在的任意字符
(3) 修改任意字符

问最少操作多少次可以把字符串T变成S？

#define MAX 1000+5 
#define same(a,b) a==b?0:1
char a[MAX],b[MAX];
int dp[MAX][MAX];
int main(){
	//freopen("yzhid.in", "r", stdin);
	scanf("%s\n%s",&a[1],&b[1]);
	int la =strlen(&a[1]),lb=strlen(&b[1]);
	for(int i=0;i<=la;i++)
		dp[i][0]=i;
	for(int i=0;i<=lb;i++)
		dp[0][i]=i;
	for(int i=1;i<=la;i++)
		for(int j=1;j<=lb;j++){
			int t =same(a[i],b[j]);
			dp[i][j]=min(dp[i-1][j-1]+t,min(dp[i-1][j]+1,dp[i][j-1]+1));
		}
	printf("%d",dp[la][lb]);		
	return 0;
}

最长单增子序列

http://www.51nod.com/tutorial/course.html#!courseId=5
(LIS Longest Increasing Subsequence)给定一个数列，从中删掉任意若干项剩余的序列叫做它的一个子序列，求它的最长的子序列，满足子序列中的元素是单调递增的。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 50000+5 
#define INF 0x3f3f3f3f
int a[MAX],f[MAX];
int bs(int *a,int len,int x){
	int b=1,e=len,mid;
	while(b<len){
		mid=(b+len)/2;
		if(a[mid]<x) b=mid+1;
		else len=mid; 
	}
	return a[b]>=x?b-1:b;
}
int main(){
	freopen("yzhid.in", "r", stdin);
	int n,m=1;//m:f's length
	scanf("%d",&n); 
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	f[0]=-INF;f[1]=a[1];
	for(int i=1;i<=n;i++){
		int x=bs(f,m,a[i]);
		f[x+1]=a[i];
		m=max(m,x+1);
	}
	printf("%d",m);
	return 0;
}

0-1背包

http://www.51nod.com/tutorial/course.html#!courseId=6
有n件物品，第i件物品(I = 1,2,3…n)的价值是vi, 重量是wi,我们有一个能承重为m的背包，我们选择一些物品放入背包，显然放入背包的总重量不超过m。我们要求选择物品的总价值最大，请问如何选择？

#define MAX 10000+5
#define INF 0x3f3f3f3f
int wi[105],pi[105],n,w,f[MAX];
int main(){
	//freopen("yzhid.in", "r", stdin);
	scanf("%d %d",&n,&w);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&wi[i],&pi[i]);
	memset(f+1,-INF,MAX);
	int ans=-INF;
	for(int i=1;i<=n;i++)
		for(int j=w;j>=wi[i];j--){
			f[j]=max(f[j],f[j-wi[i]]+pi[i]);
			ans=max(ans,f[j]);
		}
	printf("%d",ans);
	return 0;
}

正整数分组

http://www.51nod.com/tutorial/course.html#!courseId=7
将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。整数个数n<=100，所有整数的和<=10000

#define  MAX 10000+5
int a[105],f[105][MAX];
int main(){
	freopen("yzhid.in","r",stdin);
	int n,sum=0;
	scanf("%d",&n); 
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=sum/2;j++){
			if(j<a[i])
				f[i][j]=f[i-1][j];
			else if(j>=a[i]&&j<=sum/2)
				f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
		}
	int ans=(sum/2-f[n][sum/2])*2;
	if(sum%2!=0) 
		ans++;
	printf("%d",ans);	
	return 0;
}

文章目录