[kuangbin带你飞]专题十二 基础DP1

---

Monkey and BananaHDU - 1069

题意：n个砖块长宽高不同，保证上面的长和宽分别小于下面的，问能叠出的最大高度

思路：

1）设dp[i]为以i为最底层所能达到的最高高度

2）递推公式：dp[i]=max(dp[j]+a[i].z){j<i,a[j].x<a[i].x&&a[j].y<a[i].y}

3）初始化dp[i]=a[i].z

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,dp[200];
struct Brick
{
	int x,y,z;
}a[200];
bool cmp(Brick a,Brick b)
{
	if(a.x!=b.x)return a.x<b.x;
	else return a.y<b.y;
}
void init()
{
	int A,B,C;
	n*=6;
	for(int i=1;i<=n;i+=6)//6种摆法 
	{
		cin>>A>>B>>C;
		a[i+0].x=A,a[i+0].y=B,a[i+0].z=C;
		a[i+1].x=A,a[i+1].y=C,a[i+1].z=B;
		a[i+2].x=B,a[i+2].y=A,a[i+2].z=C;
		a[i+3].x=B,a[i+3].y=C,a[i+3].z=A;
		a[i+4].x=C,a[i+4].y=A,a[i+4].z=B;
		a[i+5].x=C,a[i+5].y=B,a[i+5].z=A;
	}
	sort(a+1,a+n+1,cmp);//排序保证无后效性 
	for(int i=1;i<=n;i++)dp[i]=a[i].z;
}
int main()
{
	int t=0;
	while(cin>>n)
	{
		if(n==0)return 0;
		init();
		int ans=-1;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<i;j++)
			{
				if(a[j].x<a[i].x&&a[j].y<a[i].y)
				{
					dp[i]=max(dp[i],dp[j]+a[i].z);
				}
			}
			ans=max(ans,dp[i]);
		}
		cout<<"Case "<<++t<<": maximum height = "<<ans<<endl;
	}
}

Doing Homework HDU - 1074

题意：给定n个工作，每个有截止日期和需要花费的日期，超过截止日期一天扣一分，求扣最少分方案

思路：*看到题目求路径想直接dfs但是O(15!)超时，改状压DP

免费馅饼 HDU - 1176

题意：数轴0-10的11个位置上，在t秒x位置掉？块饼，从5出发，求最多能接到的饼数量

思路：逆向dp

1）设dp[i] [j]表示第j秒到最后，在位置i能接到最多的数量

2）递推公式：dp[i] [j]=max( dp[i-1] [j+1] , dp[i-1] [j+1] , dp[i-1] [j+1] )+a[i] [j]（注意边界）

3）初始化：dp[i] [tmax]=a[i] [tmax]

4）ans=dp[5] [0]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x,t,tmax,a[11][100005],dp[11][100005];
void init()
{
	tmax=0;
	memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&t);
		a[x][t]++;
		tmax=max(tmax,t);
	}
	for(int i=0;i<=10;i++)
		dp[i][tmax]=a[i][tmax];
}
int main()
{
	while(scanf("%d",&n))
	{
		if(n==0)break;
		init();
		for(int j=tmax-1;j>=0;j--)
		{
			for(int i=0;i<=10;i++)
			{
				if(i==0)dp[i][j]=max(dp[i][j+1],dp[i+1][j+1])+a[i][j];
				else if(i==10)dp[i][j]=max(dp[i][j+1],dp[i-1][j+1])+a[i][j];
				else dp[i][j]=max(dp[i-1][j+1],max(dp[i][j+1],dp[i+1][j+1]))+a[i][j];
			}
		}
		printf("%d\n",dp[5][0]);
	}
	return 0;
}

FatMouse’s Speed HDU - 1160

题意：每个元素有两个参数a和b，找出最长子序列，使得a是严格递增的而b是严格递减的

思路：

1）设dp[i]表示以第i只老鼠作为结尾的最长子序列长度

2）递推公式：dp[i]=max(dp[j])+1{j<i,a[j]<a[i]&&b[j]>a[i]}

3）初始化dp[i]=1

4）对每个优化，记录下路径pre

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int n=0,ans=0,ansi,a[maxn],b[maxn],dp[maxn],pre[maxn];
struct node
{
	int id,a,b;
}m[maxn];
bool cmp(node x,node y)
{
	return x.a<y.a;
}
void print(int x)
{
	if(pre[x]==x)
	{
		cout<<m[x].id<<endl;
		return;		
	}
	print(pre[x]);
	cout<<m[x].id<<endl;
}
int main()
{
	int x,y;
	while(scanf("%d%d",&x,&y)!=EOF)
	{
		n++;
		m[n].id=n;
		m[n].a=x;
		m[n].b=y;
	}
	for(int i=1;i<=n;i++)
	{
		dp[i]=1;
		pre[i]=i;		
	}
	sort(m+1,m+n+1,cmp);
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(m[j].a<m[i].a&&m[j].b>m[i].b&&dp[j]+1>dp[i])
			{
				dp[i]=dp[j]+1;
				pre[i]=j;				
			}

		}
		if(ans<dp[i])
		{
			ans=dp[i];
			ansi=i;
		}
	}
	cout<<ans<<endl;
	print(ansi);
	return 0;
}

Common Subsequence POJ - 1458

题意：两个串的最长公共子序列

思路：

1）设dp[i] [j]为x串前i个（0到i-1）和y串前j个的最长公共子串长度

2）递推公式：if(x[i]==y[j])dp[i] [j]=dp[i-1] [j-1]+1

​ else dp[i] [j]=max(dp[i-1] [j],dp[i] [j-1])

3）dp[0] [0]=0

#include<iostream>
#define ll long long
using namespace std;
string x,y;
int dp[1005][1005];
int main()
{
	while(cin>>x>>y)
	{		
		for(int i=1;i<=x.length();i++)
		{
			for(int j=1;j<=y.length();j++)
			{
				if(x[i-1]==y[j-1])dp[i][j]=dp[i-1][j-1]+1;
				else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
		cout<<dp[x.length()][y.length()]<<"\n";
	}
	return 0;
}

Help Jimmy POJ - 1661

题意： 老鼠起始(x,y),空中有一些板，到达地面最快且不能摔死

思路：逆向dp，一开始设的dp [i] [j]表示(i,j)处到地面的最少时间，但是明显空间超了

正确题解 从下往上找，设dp[i] [2]，其中dp[i] [0]表示第i个平台最左边到底的最短时间，dp[i] [1]表示平台最右边到底的最短时间。

状态转移方程：dp[i] [1]=a[i].h-a[k].h+min(dp[k] [0]+a[i].x2-a[k].x1,dp[k] [1]+a[k].x2-a[i].x2)；//右

dp[i] [0]=a[i].h-a[k].h+min(dp[k] [0]+a[i].x1-a[k].x1,dp[k] [1]+a[k].x2-a[i].x1); //左

Treats for the Cows POJ - 3186

题意：给出n个数字v(i)，每次你可以取出最左边的数字或者取出最右边的数字，一共取n次取完。假设你第i次取的数字是x，那么你可以获得i*x的价值。现在你需要规划取数顺序，使得总价值和最大。

思路：

1）设dp[i] [j] [2],其中dp[i] [j] [0]表示第i次操作从左侧取下标为j的数，所能获得的最大得分，dp[i] [j] [1]表示从右侧取

2）递推公式：（注意边界）

dp[i] [j] [0]=max(dp[i-1] [j-1] [0],dp[i-1] [n-(i-j)+1] [1])+i*a[j]

dp[i] [j] [1]=max(dp[i-1] [j+1] [1],dp[i-1] [(i-1)-(n-j)] [0])+i*a[j];

别人的题解做法是区间dp

dp[i] [j] 代表从i取到j的最大总数

dp[i] [j] = max(dp[i+1] [j]+a[i] (n+i-j) , dp[i] [j-1]+a[j] (n+i-j)) 即取右边的数 取左边的数 比较哪个大

#include<iostream>
#define ll long long
using namespace std;
int n,a[2005];
int dp[2005][2005][2];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i>j)dp[i][j][0]=max(dp[i-1][j-1][0],dp[i-1][n-(i-j)+1][1])+i*a[j];
			else dp[i][j][0]=dp[i-1][j-1][0]+i*a[j];
			if(i-1>n-j)
			dp[i][j][1]=max(dp[i-1][j+1][1],dp[i-1][(i-1)-(n-j)][0])+i*a[j];
			else dp[i][j][1]=dp[i-1][j+1][1]+i*a[j];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
		}
	}
	cout<<ans<<endl;

	return 0;
}

FatMouse and Cheese HDU - 1078

题意：

有一个n*n的格子,每个格子有一个数字。
遵循以下规则:

1. 玩家每次可以由所在格子向上下左右四个方向进行直线移动，每次移动的距离不得超过m
2. 玩家下一次移动到达的格子的分值要比当前玩家所在的格子的分值要大。

求最大分数

思路：记忆化搜索

#include<bits/stdc++.h>
using namespace std;
#define ll longlong
int n,m;
int a[105][105],dp[105][105];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int dfs(int x,int y)
{
	if(dp[x][y])return dp[x][y];
	int maxx=0;
	for(int i=0;i<4;i++)
		for(int j=1;j<=m;j++)
		{
			int xx=x+dx[i]*j,yy=y+dy[i]*j;
			if(xx>0&&xx<=n&&yy>0&&yy<=n&&a[x][y]<a[xx][yy])
				maxx=max(maxx,dfs(xx,yy));
		}
	return dp[x][y]=a[x][y]+maxx;
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		if(n==-1&&m==-1)break;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&a[i][j]);
		memset(dp,0,sizeof(dp));
		
		printf("%d\n",dfs(1,1));
		
	}
	return 0;
}

Phalanx HDU - 2859

题意：求最大对称子矩阵（关于副对角线对称），输出最大的边长

思路：刚开始暴力，果然time out了[捂脸]

1）设dp[i] [j]为 以(i,j)为子矩阵的左下角，往右上方扩展的最大边长

2）状态转移

	?	?	?
	？	？	？
	对称	对称	？
j–	(i-1,j+1)	对称	？
(i,j)	i++

#include<bits/stdc++.h>
using namespace std;
#define ll longlong
int n;
char c[1005][1005];
int dp[1005][1005];
int main()
{
	std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	while(cin>>n)
	{
		if(!n)break;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				cin>>c[i][j];
		int ans=0;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dp[i][j]=1;
				int x=i,y=j;
                while(c[i][y]==c[x][j]) x--,y++;
                //这里x或y越界也不用担心，因为后面与dp[i-1][j+1]比较时会略去
                if(c[i][j+1]==c[i-1][j])
                    dp[i][j]=min(dp[i-1][j+1],i-x-1)+1;//继承右上角部分或全部
                ans=max(ans,dp[i][j]);
			}	
		}
		cout<<ans<<'\n';
	}

	
	return 0;
}

Milking TimePOJ - 3616

题意：m个时间段工作（a[i].start a[i].end a[i].v），每段工作后休息r小时，问最大工作效益

思路：

1）设dp[i]为以第i个时间段(排序后)作为结尾所能获得的最大分数

2）dp[i]=max(dp[j])+a[i].v {j<i&&a[i].s-a[j].e>=r}

3）初始化dp[i]=a[i].v

4）ans=max(dp[i])

#include<iostream>
#include<algorithm>
using namespace std;
#define ll longlong
int n,m,r,dp[1005];
struct node
{
	int s,e,v;
}a[1005];
bool cmp(node x,node y)
{
	return x.s<y.s;
}
int main()
{
	//std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>m>>r;
	for(int i=1;i<=m;i++)cin>>a[i].s>>a[i].e>>a[i].v;
	sort(a+1,a+m+1,cmp);
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		dp[i]=a[i].v;
		for(int j=1;j<i;j++)
		{
			if(a[i].s-a[j].e>=r)
			dp[i]=max(dp[i],dp[j]+a[i].v);
		}
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Making the Grade POJ - 3666

题意：给出长度为n的整数数列,修改a[i]为b[i],代价abs(a[i]-b[i]),求将其变成单调增或者单调减(不严格)的最小代价和

思路：

1）设dp[i] [j]表示前i个数满足单调，将a[i]变成 b[j]（排序去重后所有可能的a） 的最小代价和

2）dp[i] [j]=min(dp[i-1] [j])+abs(a[i]-b[j])

3）ans= dp[n] [j]

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn=2005;
ll n,m,a[maxn],b[maxn],dp[maxn][maxn];
void init()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}	
	sort(b+1,b+1+n);
	m=unique(b+1,b+n+1)-(b+1);//去重
}
ll DP()
{
	for(int i=1;i<=n;i++)
	{
		ll minn=0x7fffffff;
		for(int j=1;j<=m;j++)
		{
			minn=min(minn,dp[i-1][j]);
			dp[i][j]=minn+abs((int)(a[i]-b[j]));
		}
	}
	ll ans=0x7fffffff;
	for(int j=1;j<=m;j++)
		ans=min(ans,dp[n][j]);
	return ans;
}
int main()
{
	std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	init();
	ll tmp=DP();
	for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);//将a数组反向再跑一遍dp
	tmp=min(tmp,DP());
	cout<<tmp<<'\n';
	
	return 0;
}

交作业