Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍

【学习】DP第一弹

Jacinth posted @ 2016年8月23日 12:54 in Lerning with tags DP bzoj , 888 阅读

蒟蒻真是弱爆了

DP的姿势水平各种不足

惨啊

只能开始做被D为联赛难度的DP题惹

于是就被隔壁xmc大神各种鄙视辣

大家快去膜51nod大师：scarlet.is-programmer.com/posts/205181.html

第一弹开始辣

No. 状态
1197 Accepted
1261 Accepted
1260 Accepted
1048 Accepted
1867 Accepted
4300 Accepted
2134 Accepted
1569 Accepted
4247 Accepted
1084 Accepted
1055 Accepted
3106 Accepted

都是一些代码长度到不了1k的题大家不要围观辣

BZOJ-1197：[HNOI2006]花仙子的魔法

f[i][j]表示i个j维球的情况

首先考虑一维的情况，发现f[i][1] = 2*i 真是良心啊

然后考虑每一维只施展一次，发现f[1][i] = 2 也是资磁哦

考虑f[i][j]的转移，在已经有i-1个j维球体后，再加入一个，那么最多和原来的每个都相交一次。我们知道两个n维物体相交的部分是n-1维的（具体为什么还是dxx吧）因此最多的就是这i-1个j-1维球体全都相交在一起。

于是我们就得到： f[i][j] = f[i-1][j] + f[i-1][j-1] 作为转移方程辣

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL f[105][105];
int n,m;

int main()
{
	scanf("%d%d",&m,&n);
	for (int i=1;i<=n;++i) f[1][i] = 2ll;
	for (int i=1;i<=m;++i) f[i][1] = i*2ll;
	for (int i=2;i<=m;++i)
		for (int j=2;j<=n;++j) f[i][j] = f[i-1][j] + f[i-1][j-1];
	printf("%lld\n",f[m][n]);
	return 0;
}

BZOJ-1261: [SCOI2006]zh_tree

DP(l,r)表示[l,r]这段作为一棵树的最小访问代价。 
对于DP(l,r), 我们枚举它的根x
然后我们可以知道 $$DP(l,r) = min(DP(l, x-1)+DP(x+1, r)+C\times (sum[x]-sum[x-1])) + K\times (sum[r]-sum[l-1])$$ [sum[i]为输入的前缀和]
记忆化优化一下就资磁辣
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int NN = 35;
int n,sum[NN];
bool vis[NN][NN];
double k,c,f[NN][NN];

double DP(int l,int r)
{
	if (l>r) return 0;
	if (vis[l][r]) return f[l][r];
	vis[l][r] = 1;
	double &ans = f[l][r];
	ans = 1e20;
	for (int i=l;i<=r;++i)
		ans = min(ans, DP(l,i-1) + DP(i+1,r) + c*(sum[i] - sum[i-1]) / sum[n]);
	return ans += k*(sum[r] - sum[l-1]) / sum[n];
} 
int main()
{
	scanf("%d%lf%lf",&n,&k,&c);
	sum[0] = 0;
	for (int i=1;i<=n;++i) scanf("%d",&sum[i]), sum[i] += sum[i-1];
	memset(vis,0,sizeof(vis));
	printf("%.3lf\n",DP(1,n));
	return 0;
}

BZOJ-1260: [CQOI2007]涂色paint

f[i][j]表示i到j一段的最少涂色次数

枚举字符串的长度l以及起点i，则 j = i+l;

初始状态呢就是 f[i][i] = 1; f[i][i+1] = (ch[i] == ch[i+1]);

若ch[i] == ch[j] 则 f[i][j] = min{f[i+1][j],f[i][j-1],f[i+1][j-1]+1}

若ch[i] != ch[j] 则 f[i][j] = min{f[i][k] + f[k+1][j]} 其中i<=k<j

#include <bits/stdc++.h>
using namespace std;
char ch[55];
int f[55][55],n;
int main()
{
	scanf("%s", ch+1);
	n = strlen(ch+1);
	memset(f,0x3f,sizeof(f));
	for (int i=1;i<=n;++i) f[i][i] = 1;
	for (int l=1;l<=n;++l)
		for (int i=1;i<=n-l;++i)
		{
			int j=i+l;
			if (ch[i] == ch[j])
			{
				if (l == 1) f[i][i+1] = 1;
				else
				f[i][j] = min(f[i][j-1],f[i+1][j]),	f[i][j] = min(f[i][j],f[i+1][j-1]+1);
			}
			else
			for (int k=i;k<j;++k) f[i][j] = min(f[i][j],f[i][k] + f[k+1][j]);
		}
	printf("%d\n",f[1][n]);
	return 0;
}

BZOJ-1048: [HAOI2007]分割矩阵

记忆化搜索题，但还是丢到这里辣

f[a][b][c][d][l] 表示在(a,c),(b,d)间分成l块的结果

然后数据辣么小，记忆花搜一搜就过辣

double 赋初值还要写循环qaq

#include <bits/stdc++.h>
using namespace std;
const int N = 12;
int n,m,k,a[N][N],sum[N][N];
double f[N][N][N][N][N],ave;

double sqr(double xx) { return xx * xx; }

double DFS(int a,int b,int c,int d,int l)
{
	double &pre = f[a][b][c][d][l];
	if (pre != -1) return pre;
	if (l == 0)
	{
		pre = sum[b][d] + sum[a-1][c-1] - sum[a-1][d] - sum[b][c-1];
		pre = sqr(pre - ave);
		return pre;
	}
	pre = 1e9;
	for (int i=a+1;i<=b;++i)
		for (int j=0;j<l;++j) pre = min(pre,DFS(a,i-1,c,d,j) + DFS(i,b,c,d,l-j-1));
	for (int i=c+1;i<=d;++i)
		for (int j=0;j<l;++j) pre = min(pre,DFS(a,b,c,i-1,j) + DFS(a,b,i,d,l-j-1));
	return pre;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for (int i=0;i<=10;++i)
		for (int b=0;b<=10;++b)
			for (int c=0;c<=10;++c)
				for (int d=0;d<=10;++d)
					for (int l=0;l<=10;++l) f[i][b][c][d][l] = -1;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) scanf("%d",&a[i][j]);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
	ave = (double)sum[n][m] / k;
	DFS(1,n,1,m,k-1);
	printf("%.2lf\n",sqrt(f[1][n][1][m][k-1]/k));
	return 0;
}

BZOJ-1867: [Noi1999]钉子和小球

好古老的题目哎，感觉比苯宝宝的年龄大到不知道哪里去了

不能输出回车难过（？！）

然后分数很难过（第一次写，一言不合就自爆辣）

f[i][j]表示小球落在第i行第j个钉子上的概率

如果一个点有钉子 f[i+1][j] 和 f[i+1][j+1]平分这个点的概率（就是乘1/2）

如果一个点没有钉子 f[i+2][j+1] 得到这个点的全部概率

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

struct fr
{
	LL nn,dd;
	fr(LL _=0,LL __=1) : nn(_),dd(__) {}
}f[60][60];

LL GCD(LL xx,LL yy)
{
	return yy?GCD(yy,xx%yy):xx;
}

void Reduction(fr &xx)
{
	LL gcd=GCD(xx.nn,xx.dd);
	xx.nn /= gcd;
	xx.dd /= gcd;
}

fr operator + (const fr &xx, const fr &yy)
{
	fr zz;
	LL gcd = GCD(xx.dd,yy.dd);
	zz.dd = xx.dd/gcd*yy.dd;
	zz.nn = xx.nn*(yy.dd/gcd) + yy.nn*(xx.dd/gcd);
	Reduction(zz);
	return zz;
}
fr operator * (const fr &xx, const fr &yy)
{
	fr zz(xx.nn*yy.nn,xx.dd*yy.dd);
	Reduction(zz);
	return zz;
}
void operator += (fr &xx, const fr &yy)
{
	xx = xx+yy;
}

ostream& operator << (ostream &os,const fr &x)  
{  
	os<<x.nn<<'/'<<x.dd;  
	return os;  
}

bool Get_c()
{
	char c;
	for (c=getchar();c==' '||c=='\n'||c=='\r'||c=='\t';c=getchar());
	if (c == '*') return 1; else return 0;
}

bool mp[60][60];
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=i;++j)	mp[i][j] = Get_c();
	f[1][1] = fr(1,1);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
		if (mp[i][j])
			f[i+1][j] += f[i][j] * fr(1,2), f[i+1][j+1] += f[i][j] * fr(1,2);
		else f[i+2][j+1] += f[i][j];
	cout<<f[n+1][m+1];
	return 0;
}

BZOJ-4300: 绝世好题

对于每一位弄一弄就好辣（文化课好题过敏体质）

#include <bits/stdc++.h>
using namespace std;

int ans,tmp,n,x,bin[32],f[32];

int main()
{
	scanf("%d",&n);
	for (int i=0;i<=30;++i) bin[i] = 1<<i;
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		tmp = 0;
		for (int j=0;j<=30;++j)
			if (x&bin[j]) tmp = max(tmp,f[j] + 1);
		for (int j=0;j<=30;++j)
			if (x&bin[j]) f[j] = tmp;
		ans = max(ans,tmp);
	}
	printf("%d\n",ans);
	return 0;
}

BZOJ-2134: 单选错位

相邻的两个题期望得分为 1.0/max(a[i],a[i-1] + 1); 边读入边算很资磁哦

#include <bits/stdc++.h>
using namespace std;

int n,A,B,C,x,y,sta,tmp;
double ans;

int main()
{
	scanf("%d%d%d%d%d",&n,&A,&B,&C,&x);
	y = sta = x;
	for (int i=2;i<=n;++i)
	{
		x = ((long long)x * A + B) % 100000001;
		tmp = x%C + 1;
		ans += 1.0/max(tmp,y%C+1);
		y = x;
	}
	printf("%.3lf",ans + 1.0/max(sta%C+1,x%C+1));
	return 0;
}

BZOJ-1569: [JSOI2008]Blue Mary的职员分配

定义状态f[i][A][B][p] 为这一状态下的最小答案。
表示状态现有i名员工，有A金钱，有B声誉,招新状态为p。
转移时需枚举当前的j个人有多少去赚钱，有多少去赚声誉。
k=0,3时 此时更新状态 （ii,xx,yy,0），（ii,xx-z,yy,1）；
k=1,2时    更新状态（ii,xx,yy,p+1）（表示不能招人）；
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int n,x,y,z,A,B,aa,ans,f[35][25][25][5];

void Work(int a,int b,int c,int d,int i,int j,int k,int p)
{
	if (b < 0) return;
	if (b > aa) b = aa;
	if (c > B) c = B;
	f[a][b][c][d] = min(f[a][b][c][d],f[i][j][k][p] + 1);
}
int main()
{
	scanf("%d%d%d%d%d%d",&n,&x,&y,&z,&A,&B);
	aa = max(A,z);
	memset(f,0x3f,sizeof(f));
	f[n][0][0][0] = 0;
	ans = INF;
	for (int i=n;i<=34;++i)
		for (int p=0;p<=3;++p)
			for (int j=0;j<=aa;++j)
				for (int k=0;k<=B;++k)
				if (f[i][j][k][p] != INF)
				{
					if (j>=A && k>=B)
					{
						ans = min(ans,f[i][j][k][p]);
						continue;
					}
					if (f[i][j][k][p] > ans) continue;
					for (int q = 0;q<=i;++q)
					{
						int xx = j+q*x, yy = k+(i-q)*y,ii = i;
						if (p == 3) ii ++;
						if (p ==0 || p == 3)
						{
							Work(ii,xx,yy,0,i,j,k,p);
							Work(ii,xx-z,yy,1,i,j,k,p);
						}
						else Work(ii,xx,yy,p+1,i,j,k,p);
					}
				}
	printf("%d\n",ans);
	return 0;
}

BZOJ-4247: 挂饰

有大神说背包不算DP（？！）（对对对，就是隔壁xmc）

因为有可能前面好多没有挂钩的物品，所以上来要排个序

f[i][j]表示前i个物品剩j个挂钩的最大美观，然后转移就可以很资磁辣

#include <bits/stdc++.h>
using namespace std;

struct A
{
	int num,s;
}a[2020];
int f[2020][2020],n,ans;

bool cmp(A xx,A yy)
{
	return xx.num > yy.num;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d%d",&a[i].num,&a[i].s);
	sort(a+1,a+1+n,cmp);
	memset(f,-63,sizeof(f));
	f[0][1] = 0;
	for (int i=1;i<=n;++i)
		for (int j=0;j<=n;++j)
			f[i][j] = max(f[i-1][j],f[i-1][max(j-a[i].num,0)+1]+a[i].s);
	for (int i=0;i<=n;++i) ans = max(ans,f[n][i]);
	printf("%d\n",ans);
	return 0;
}

BZOJ-1084: [SCOI2005]最大子矩阵

由于1≤m≤2的神奇设定，我们根据m分开来玩就可以了

对，就是分！开！来！（前缀和搞搞还是蛮容易的）

#include <bits/stdc++.h>
using namespace std;
const int NN = 105;
int n,m,k,x,s[NN],s1[NN],s2[NN],dp[NN][11],f[NN][NN][11];

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	if (m == 1)
	{
		for (int i=1;i<=n;++i) scanf("%d",&x), s[i] = s[i-1] + x;
		for (int i=1;i<=n;++i)
			for (int w=1;w<=k;++w)
			{
				dp[i][w] = dp[i-1][w];
				for (int j=0;j<i;++j)
					dp[i][w] = max(dp[i][w], dp[j][w-1] + s[i] - s[j]);
			}
		printf("%d\n",dp[n][k]);
	}
	else
	{
		for (int i=1;i<=n;++i)
			scanf("%d",&x), s1[i] = s1[i-1] + x, scanf("%d",&x), s2[i] = s2[i-1] + x;
		for (int w=1;w<=k;++w)
			for (int i=1;i<=n;++i)
				for (int j=1;j<=n;++j)
				{
					f[i][j][w] = max(f[i-1][j][w], f[i][j-1][w]);
					for (int l=0;l<i;++l)
						f[i][j][w] = max(f[i][j][w], f[l][j][w-1]+s1[i]-s1[l]);
					for (int l=0;l<j;++l)
						f[i][j][w] = max(f[i][j][w], f[i][l][w-1]+s2[j]-s2[l]);
					if (i == j)
					for (int l=0;l<i;++l)
						f[i][j][w] = max(f[i][j][w], f[l][l][w-1] + s1[i]-s1[l]+s2[i]-s2[l]);
				}
		printf("%d\n",f[n][n][k]);
	}
	return 0;
}

BZOJ-1055: [HAOI2008]玩具取名

其实就是记忆化搜索辣

记忆化搜索f[l][r][k]表示l-r能否合成字母k
如果k可以变成ab且 ( f[l][j][a] & f[j+1][r][b] )（l <= j < r） 则f[l][r][k] = 1
#include <bits/stdc++.h>
using namespace std;

char p[4]={'W','I','N','G'};
int t[4],f[205][205][4],a[4][20][2],n;
char ch[205];
bool flag;

bool DP(int l,int r,int k)
{
	if (l == r) return (ch[l] == p[k]);
	if (f[l][r][k] != -1) return f[l][r][k];
	for (int i=1;i<=t[k];++i)
	{
		for (int j=l;j<r;++j)	
			if (DP(l,j,a[k][i][0]) && DP(j+1,r,a[k][i][1]))
				return f[l][r][k] = 1;
	}
	return f[l][r][k] = 0;
}

int Change(char c)
{
	switch (c)
	{
		case 'W' : return 0; break;
		case 'I' : return 1; break;
		case 'N' : return 2; break;
		case 'G' : return 3; break;
	}	
}

int main()
{
	memset(f,-1,sizeof(f));
	for (int i=0;i<4;++i) scanf("%d",&t[i]);
	for (int i=0;i<4;++i)
		for (int j=1;j<=t[i];++j)
		{
			scanf("%s",ch);
			a[i][j][0] = Change(ch[0]);
			a[i][j][1] = Change(ch[1]);
		}		
	scanf("%s",ch+1);
	n = strlen(ch+1);
	flag = 0;
	for (int i=0;i<4;++i)
		if (DP(1,n,i)) flag = 1, putchar(p[i]);
	if (!flag) puts("The name is wrong!");
	return 0;
}

BZOJ-3106: [cqoi2013]棋盘游戏

f[a][b][c][d][x][y]表示白在（a,b），黑在（c,d），走了x步，状态为y

由于黑棋腿长（？！），所以欺负白棋只能在第一步赢，否则只能延长死亡时间而不能赢游戏（这真TM不讲道理）

转移的时候考虑黑棋尽量让步数少，而白棋尽量让步数大就好啦

#include <bits/stdc++.h>
using namespace std;
const int N=21;
#define INF 0x3f3f3f3f
int f[N][N][N][N][N*3][2],n,r1,c1,r2,c2;

int DFS(int a,int b,int c,int d,int x,int y)
{
	if (x > n*3) return INF;
	if (a == c && b == d) return y == 1?INF:0;
	if (f[a][b][c][d][x][y]) return f[a][b][c][d][x][y];
	int &ans = f[a][b][c][d][x][y];
	if (y == 0)
	{
		if (a>1) ans = max(ans,DFS(a-1,b,c,d,x+1,1)+1);
		if (b>1) ans = max(ans,DFS(a,b-1,c,d,x+1,1)+1);
		if (a<n) ans = max(ans,DFS(a+1,b,c,d,x+1,1)+1);
		if (b<n) ans = max(ans,DFS(a,b+1,c,d,x+1,1)+1);
	}
	else
	{
		ans = INF;
		if (c>1) ans = min(ans,DFS(a,b,c-1,d,x+1,0) +1);
		if (d>1) ans = min(ans,DFS(a,b,c,d-1,x+1,0) +1);
		if (c<n) ans = min(ans,DFS(a,b,c+1,d,x+1,0)+1);
		if (d<n) ans = min(ans,DFS(a,b,c,d+1,x+1,0)+1);
		if (c>2) ans = min(ans,DFS(a,b,c-2,d,x+1,0)+1);
		if (d>2) ans = min(ans,DFS(a,b,c,d-2,x+1,0)+1);
		if (c+2<=n) ans = min(ans,DFS(a,b,c+2,d,x+1,0)+1);
		if (d+2<=n) ans = min(ans,DFS(a,b,c,d+2,x+1,0)+1);
	}
	return ans;
}
int main()
{
	scanf("%d%d%d%d%d",&n,&r1,&c1,&r2,&c2);
	if (abs(r1-r2) + abs(c1-c2) == 1) puts("WHITE 1");
	else DFS(r1,c1,r2,c2,0,0), printf("BLACK %d\n",f[r1][c1][r2][c2][0][0]);
	return 0;
}

 

更新好累啊= =|

所以第一弹就先更11道辣

敬请期待第二弹

Small_feed 评论 (2)
1
[回复]
Avatar_small
Flandre Scarlet 说:
2016年8月27日 10:08

%%%DP大师
还有我怎么就说背包不是DP了
还有我怎么就隔壁了

2
[回复]
Avatar_small
Jacinth 说:
2016年8月29日 21:30

@Flandre Scarlet: 怎么记得泥切51nod的时候怒D过背包。 隔壁只是因为泥挂在友链墙上QAQ %%%DP大师Scarlet


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter