第三弹辣

屯的题快写完辣(✿◡‿◡)

开森~~O(∩_∩)O~~

第三弹开始辣

BZOJ-1019: [SHOI2008]汉诺塔

f[x][i],g[x][i] 分别表示当前x柱上有i个圆盘，将它们移至任意另一个柱的操作数，和另一柱子的编号。

f[x][i],g[x][i] 可由 f[][i-1],g[][i-1] 推得：

我们令 y = g[x][i-1] , z = 6-x-y;

1)x上i-1个圆盘移至y上

2)将x上的第i个圆盘，移至z

此时 f[x][i] = f[x][i-1] + 1;

然后我们再次移动y上的i-1个，此时进行分类讨论

当 f[y][i-1] == z 移到z后，全过程结束。 此时 f[x][i] += f[y][i-1], g[x][i] = z;

当 f[y][i-1] == x 我们需要将i-1个圆盘移至x，再将z上的第i个圆盘，移至y。因为g[x][i-1] == y，所以x上i-1个圆盘已经移动到y，全过程结束。此时 f[x][i] += f[y][i-1] + f[x][i-1] + 1, g[x][i] = y;

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int g[5][50],n;
char ch[50];
bool vis[10]={0};
LL f[5][50];

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=6;++i)
	{
		scanf("%s",ch);
		int l = ch[0] - 'A' + 1, r = ch[1] - 'A' + 1;
		if (!vis[l]) vis[l] = 1, g[l][1] = r, f[l][1] = 1;
	}
	for (int i=2;i<=n;++i)
	{
		for (int x=1;x<=3;++x)
		{
			int y = g[x][i-1], z = 6-y-x;
			f[x][i] = f[x][i-1] + 1;
			if (z == g[y][i-1])
			{
				f[x][i] += f[y][i-1], g[x][i] = z;
			}
			else
			{
				f[x][i] += f[y][i-1] + f[x][i-1] + 1;
				g[x][i] = y;
			}
		}
	}
	printf("%lld\n",f[1][n]);
	return 0;
}

BZOJ-1996: [Hnoi2010]chorus 合唱队

f[i][j][0/1]表示取到数列中从i到j的区间，上一个取到的是数列左边/右边的数

f[i][j][0]=f[i+1][j][0]*(a[i]<a[i+1])+f[i+1][j][1]*(a[i]<a[j])

f[i][j][1]=f[i][j+1][0]+(a[j]>a[i])+f[i][j+1][1]*(a[j]>a[j-1])

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int mod = 19650827,NN = 1005;
int a[NN],f[NN][NN][2],n;

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

BZOJ-1864: [Zjoi2006]三色二叉树

树形DP

先一遍DFS把树造粗来

0/1/2分别表示不同的颜色，f存最大值，g存最小值

DP一下就粗来辣~\(≧▽≦)/~

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int NN = 500050;
char ch[NN];
int root,f[NN][3],g[NN][3],tr[NN][2],cnt = 0;

void DFS(int &xx)
{
	xx = ++cnt;
	int tmp = ch[cnt]-'0';
	if (tmp) DFS(tr[xx][0]);
	if (tmp > 1) DFS(tr[xx][1]);
}

void DP(int xx)
{
	if (!xx) return;
	int l = tr[xx][0],r = tr[xx][1];
	DP(l), DP(r);
	for (int i=0;i<3;++i)
	{
		int x = (i+1) % 3, y =(x+1) % 3, z = (i) ? 0:1;
		f[xx][i] = max(f[l][x] + f[r][y], f[l][y] + f[r][x]) + z;
		g[xx][i] = min(g[l][x] + g[r][y], g[l][y] + g[r][x]) + z;
	}
}

int main()
{
	scanf("%s",ch+1);
	DFS(root);
	DP(1);
	printf("%d %d\n",max(f[1][0],max(f[1][1],f[1][2])),min(g[1][0],min(g[1][1],g[1][2])));
	return 0;
}

BZOJ-2660: [Beijing wc2012]最多的方案

首先可以发现斐波那契数非常少，然后我们可以预处理出这些斐波那契数，然后先贪心的去选用尽可能大的斐波那契数去构成这个数。

OIER都知道每个斐波那契数都可以用它之前的两个数替换。

dp[i][1/0]表示dp到第i个贪心选出来的斐波那契数，并且选/不选这个数的方案。

sum[i]表示一个前缀和。sum[j]-sum[i-1]表示第i个数到第j个数之间空出来多少个斐波那契数。

于是我们可以得到：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int cnt;
LL f[110],n,dp[110][2],sum[110];
int main()
{
	scanf("%lld",&n);
	f[1] = 1ll, f[2] = 2ll;
	for (cnt=2;f[cnt] < n;) ++cnt, f[cnt] = f[cnt-1] + f[cnt-2];
	for (int i=cnt;i;i--) if (n >= f[i]) n -= f[i], sum[++sum[0]] = i;
	sort(sum+1,sum+1+sum[0]);
	dp[1][1] = 1;
	dp[1][0] = (sum[1] - 1)/2ll;	
	for (int i=2;i<=sum[0];++i)
	{
		dp[i][1] = dp[i-1][0] + dp[i-1][1];
		dp[i][0] = dp[i-1][1] * ((sum[i]-sum[i-1]-1)/2ll) + dp[i-1][0] * ((sum[i]-sum[i-1])/2ll);
	}
	printf("%lld\n",dp[sum[0]][1] + dp[sum[0]][0]);
	return 0;
}

BZOJ-2423: [HAOI2010]最长公共子序列

第一问和正常的最长公共子序列一样滴

当 ch1[i] == ch2[j] 时 f[i][j] = f[i-1][j-1] + 1;

当 ch1[i] != ch2[j] 时 f[i][j] = max(f[i-1][j],f[i][j-1]);

考虑方案数

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

const int mod = 100000000, NN = 5050;
char ch1[NN],ch2[NN];
int f[2][NN],g[2][NN],l1,l2,t,la;


int main()
{
	scanf("%s",ch1+1);
	l1 = strlen(ch1+1) - 1;
	scanf("%s",ch2+1);
	l2 = strlen(ch2+1) - 1;
	for (int i=1;i<=l2;++i) g[1][i] = 1;
	t = 1, la = 0;
	g[t][0] = 1;
	for (int i=1;i<=l1;++i)
	{
		t ^= 1, la ^= 1;
		g[t][0] = 1;
		for (int j=1;j<=l2;++j)
		{
			if (ch1[i] == ch2[j])
			{
				f[t][j] = f[la][j-1] + 1;
				g[t][j] = g[la][j-1] % mod;
				if (f[t][j] == f[la][j]) g[t][j] = (g[t][j] + g[la][j]) % mod;
				if (f[t][j] == f[t][j-1]) g[t][j] = (g[t][j] + g[t][j-1]) % mod;
			}
			else
			{
				f[t][j] = max(f[la][j],f[t][j-1]);
				if (f[t][j] == f[la][j]) g[t][j] = (g[t][j] + g[la][j]) % mod;
				if (f[t][j] == f[t][j-1]) g[t][j] = (g[t][j] + g[t][j-1]) % mod;
				if (f[t][j] == f[la][j-1]) g[t][j] = (g[t][j] - g[la][j-1] + mod) % mod;
			}
		}
		memset(f[la],0,sizeof(f[la]));
		memset(g[la],0,sizeof(g[la]));
	}
	printf("%d\n%d\n",f[t][l2],g[t][l2]);
	return 0;
}

BZOJ-4321: queue2

状态好难设计，蒟蒻狗带辣

f[i][j][0/1] 表示1..i排完队，j对不满足条件的人，i和i-1是否靠在一起的方案数

转移就舒服多辣

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int NN = 1005,mod = 7777777;
int n;
LL f[NN][NN][2];

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

BZOJ-1087: [SCOI2005]互不侵犯King

状压DP

f1[i]表示i状态是否合法（即一行内是否有相邻的王）

f2[i][j]表示i,j状态相互是否合法（即相邻两行间是否符合王的要求）

cnt[i]表示i状态下王的个数。

预处理出f1,f2,cnt。

dp[j][p][k]表示第j行，p个王，状态为k

由于n好小啊，所以就状压辣

转移还是很方便的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
 
int m,n,all,cnt[513];
LL ans,dp[10][100][513];
bool f1[513],f2[513][513];
 
void Pre()
{
    int sum;
    for (int i=0;i<=all;++i)
        if ((i & (i>>1)) == 0)
        {
            sum = 0;
            for (int x=i;x;x>>=1) sum += (x & 1);
            cnt[i] = sum, f1[i] = 1;
        }
    for (int i=0;i<=all;++i)
    if (f1[i])
        for (int j=0;j<=all;++j)
        if (f1[j])
        {
            if (((i&j) == 0) && ((i&(j>>1)) == 0) && ((j&(i>>1)) == 0))
            f2[i][j] = 1;
        }
}
 
int main()
{
    scanf("%d%d",&n,&m);
    all = (1<<n) - 1;
    Pre();
    for (int i=0;i<=all;++i)
        if (f1[i]) dp[1][cnt[i]][i] = 1;
    for (int j=1;j<n;++j)
        for (int k=0;k<=all;++k)
        if (f1[k])
            for (int i=0;i<=all;++i)
                if (f1[i] && f2[k][i])
                    for (int p=cnt[k];p+cnt[i]<=m;++p)
                        dp[j+1][p+cnt[i]][i] += dp[j][p][k];
    ans = 0ll;
    for (int i=0;i<=all;++i) ans += dp[n][m][i];
    printf("%lld\n",ans);
    return 0;
}

BZOJ-1090: [SCOI2003]字符串折叠

f[l][r]为l~r的最短折叠长度

f[l][r] = min(r-l+1, f[l][i]+f[i+][r]) (l<=i<=r)

考虑 i+1~r 可以由 l~i 重复得到，那么此时的长度为 (f[l][i] + 2 + Get_ws((r-i) / (i-l+1)+1))

和原先的 f[l][r] 取 min 即可得到

全过程用记忆化搜索可以实现辣

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
using namespace std;

const int NN = 105;

int f[NN][NN];
char ch[NN];
bool mark[NN][NN]={0};

bool Jug(int l,int r,int L,int R)
{
	if ((r-l+1) % (R-L+1) != 0) return 0;
	for (int i=l;i<=r;++i)
		if (ch[i] != ch[(i-l) % (R-L+1) + L]) return 0;
	return 1;
}

int Get_ws(int xx)
{
	int tmp = 0;
	while (xx) xx/=10 , ++tmp;
	return tmp;
}

int DP(int l,int r)
{
	if (l == r) return 1;
	if (mark[l][r]) return f[l][r];
	mark[l][r] = 1;
	int tmp = (r-l+1);
	for (int i=l;i<r;++i)
	{
		tmp = min(tmp,DP(l,i)+DP(i+1,r));
		if (Jug(i+1,r,l,i)) tmp = min(tmp,DP(l,i) +2 +Get_ws((r-i) / (i-l+1)+1));
	}
	return f[l][r] = tmp;
}

int main()
{
	scanf("%s",ch);
	printf("%d\n",DP(0,strlen(ch)-1));
	return 0;
}

BZOJ-1801: [Ahoi2009]chess 中国象棋

f[i][j][k] 表示已经排了i排，有j列有一颗棋子，有k列有两颗棋子的方案数

考虑第i排放1/2颗棋子，由第i-1排转移

放一颗：使 j-1,k -> j,k (放在没有棋子的列上) / j+1,k-1 -> j,k（放在有一颗棋子的列上）

放两颗：使 j-2,k -> j,k (放在没有棋子的列上) / j+2,k-2 -> j,k (放在有一颗棋子的列上) / j-1+1,k-1 -> j,k (一颗放在有一颗棋子的列上，另一颗放在没有棋子的列上)

组合数乘一乘就好辣

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int NN = 105,mod = 9999973;
LL f[NN][NN][NN],n,m,ans;

int main()
{
	scanf("%lld%lld",&n,&m);
	if (m > n) swap(n,m);
	f[0][0][0] = 1;
	ans = 0ll;
	for (int i=1;i<=n;++i)
	{
		for (LL j=0;j<=m;++j)
			for (LL k=0;k<=m-j;++k)
			{
				//1
				f[i][j][k] = f[i-1][j][k];
				if (j>0) f[i][j][k] = (f[i][j][k] +f[i-1][j-1][k] *(m-j-k+1ll) % mod) %mod;
				if (j<m && k>0) f[i][j][k] = (f[i][j][k] +f[i-1][j+1][k-1] *(j+1ll) %mod) %mod;
				//2
				if (j>1) f[i][j][k] = (f[i][j][k] +f[i-1][j-2][k] *((m-j-k+2ll)*(m-j-k+1ll)/2ll) %mod) %mod;
				if (j<m-1 && k>1) f[i][j][k] = (f[i][j][k] +f[i-1][j+2][k-2] * ((j+2ll)*(j+1ll)/2ll) %mod) %mod;
				if (j>0 && k>0) f[i][j][k] = (f[i][j][k] +f[i-1][j][k-1] *j %mod *(m-j-k+1ll) %mod) %mod;
			}
	}
	for (int j=0;j<=m;++j)
		for (int k=0;k<=m-j;++k) ans = (ans + f[n][j][k]) % mod;
	printf("%lld\n",ans);
	return 0;
}

1899: [Zjoi2004]Lunch 午餐

先对所有人按照吃饭时间的长短进行排序，易得吃饭时间越长的应该越早打饭，以此进行DP；

f[i][j] 表示第i个人，一队点餐所花费的时间为j的状态下，最少的时间

考虑这个人加入： //sum为排队时间的前缀和

若加入一队，该队新的花费时间为 当前点餐时间j+此人点餐时间+此人用餐时间

若加入二队，该队新的花费时间为 此人及以前所有人的点餐时间sum[i]-当前点餐时间j+此人用餐时间

转移搞一搞就可以辣

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

const int NN = 205;

int n,ans,sum[NN]={0},f[NN][NN*NN];
struct A
{
	int x,y;
}a[NN];

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

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

BZOJ-1237: [SCOI2008]配对

要是可以相同配对就是水题辣(╯‵□′)╯︵┻━┻

然而题目坑爹还是要做啊~~~~(>_<)~~~~

听说每个数和它配对的数位置只可能相差2。

然后我们就可以大力分类讨论不要虚辣。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
#define INF 21000000000000000ll
typedef long long LL;
const int NN = 100005;
LL a[NN],b[NN],f[NN];
int n;

LL Cal(LL xx,LL yy)
{
	if (xx == yy) return INF;
	else return abs(xx-yy);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%lld%lld",&a[i],&b[i]);
	if (a[1] == b[1] && n == 1)
	{
		puts("-1");
		return 0;
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	f[1] = Cal(a[1],b[1]) ;
	f[2] = min(f[1]+Cal(a[2],b[2]),Cal(a[1],b[2])+Cal(a[2],b[1]));
	for (int i=3;i<=n;++i)
	{
		f[i] = f[i-1] + Cal(a[i],b[i]);
		f[i] = min(f[i],f[i-2]+Cal(a[i-1],b[i])+Cal(b[i-1],a[i]));
		f[i] = min(f[i],f[i-3]+Cal(a[i-2],b[i])+Cal(a[i-1],b[i-1])+Cal(a[i],b[i-2]));
		f[i] = min(f[i],f[i-3]+Cal(a[i-2],b[i-1])+Cal(a[i-1],b[i])+Cal(a[i],b[i-2]));
		f[i] = min(f[i],f[i-3]+Cal(a[i-2],b[i])+Cal(a[i-1],b[i-2])+Cal(a[i],b[i-1]));
	}
	printf("%lld\n",f[n]);
	return 0;
}