QBXT Day 2 记录

例题1：乌龟棋

略

例题2： noip2015 子串

有两个仅包含小写英文字母的字符串 A 和 B。

现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串,

请问有多少种方案可以使得这个新串与字符串 B 相等?注意:子串取出的位置不同也认为是不同的方案。

设f[i][j][k][1/0]表示到了A第i位，B第j位，选了K个，1/0选育不选

转移：就是照着状态转移

a[i]==b[j]:dp[i][j][k][1]=dp[i-1][j-1][k-1][0]+dp[i-1][j-1][k][1]

else:dp[i][j][k][1]=0

dp[i][j][k][0]=dp[i-1][j][k][0]+dp[i][j][k][1]

为了节约空间，第一位可以滚掉

例题3

有一个数列，请你改变尽可能少的数，使得这个数列变成递增的

观察一下性质，没两个数之间的差必须要大于一

也就是，我们要使得\(a_j-a_i>=j-i\) 

移向

\(a_j-j>=a_i-i\)

然后我们求一个\(a_i-i\)最长下降子序列，然后总长度一减就可以了。

发现性质最重要

例题4

折叠的定义如下：

一个字符串可以看成它自身的折叠。
X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
折叠之后的字符串可以连接和再次折叠。

给一个字符串，求它的最短折叠长度。

例如：3(A)C2(B) = AAACBB

2(3(A)C)2(B)=AAACAAACBB

AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD

NEERCYESYESYESNEERCYESYESYES的最短折叠为：2(NEERC3(YES))

区间dp，套模板就可以了。

然后在转移的时候还要判断整个区间是否可以折叠，怎么判断：暴力

然后是背包dp

先是01/完全/多重背包的板u子

多重背包单调队列优化。

首先我们来看转移

f[i]要可以从一下几个状态转移而来

f[i-v[j]1]+w[j]1 and f[i-v[j]2]+w[j]2.........f[i-v[j]num[j]]+w[j]num[j]

然后我们将i变成一个a+b*v[j]的形式再来看一看

f[(b-1)v[j]+a]+w[j]1 and f[(b-2)v[j]+a]+w[j]2 ...................

然后我们同时减去b*w[j]

{f[(b-1)v[j]+a]+w[j](b-1) and f[(b-2)v[j]+a]+w[j](b-2)}+b*w[j] ...................

然后我们发现，如此操作以后，花括号内加的w[j]只与其位置有关，然后我们要求最大值，就可以单调队列

需要两个队列（一个也可以) ，一个是单调队列，一个是储存当前所有可以拓展的状态

两重循环，第一重枚举上面的a，队列清空

第二重枚举b,并且维护队列

int q1[maxn],q2[maxn]; //队列，q1为原始队列，q2为单调队列

int pack(int *f,int V,int v,int w,int num)//f为dp数组，V是总体积，v是单个物品的体积，w是单个物品的价值，num为数量

{

	for(int d=0;d<v;d++)//枚举a

	{

		int t1=-1,t2=-1,h1=0,h2=0;//队列置空

		for(int k=d,i=0;k<=V;k+=v,i++)//枚举b，并且算出当前的体积

		{//因为我们将上一次的dp值存在队列里了，所以就不用倒序了

			if(t1-h1+1==num)//如果队列满了

			{

				if(q1[h1]==q2[h2])	h2++;//看看单调队列是否要出队

				h1++;

			}

			int pas=f[k]-i*w;//如此操作

			while(t2>=h2&&q2[t2]<pas)	t2--;

			q2[++t2]=pas;//维护

			q1[++t1]=pas;

			f[k]=q2[h2]+i*w;//补回来

		}

	}

}

例题1

题意

有n个人参加拔河比赛，要把他们分为两组，每人的实力为ai，一组的实力为这组人的实力之和。求两队实力差的最小值。（两队的人数没有限制）

我们该如何使用01背包的板子进行套用ne ?

我们将每个人的实力看作容积，然后价值就全是单位1

然后我们使所有人的实力之和作为总容积

然后再输出答案。输出总体积>>1 的所能装载的最大价值。

这样的话，我们就求得最接近实力值总和>>1的方案所需要的最多人数。

这样的话就求除了最优解

例题2

开始有一个数begin，给一个长为n的序列，ci，每次操作可以选择把开始的数加或减ci，变为新的数，之后再上一次的数的基础上加或减。

要求每次操作之后的数要大于等于0，小于等于max，求最后一次操作之后这个数的最大值。如果没有满足要求的解输出-1.

设f[i][j]表示第i轮，j可不可行。然后转移一下就可以了。

其他

询问1~n之间所有数字中1的个数和。例如11011中有4个数位1。

然后套一个数位dp就可以了。

#include<cstdio>

#include<iostream>

#include<algorithm>

long long f[20];

long long n;

long long ans;

void solve(long long t,long long s)

{

	if(t==1)

	{

		for(int i=0;i<=n%10;i++)

			if(i==1)	ans+=1;

		return ;

	}

	long long now=(n/t)%10;

	for(int i=0;i<now;i++)

	{

		if(i==1)	ans+=t;

		ans+=f[s-1];

	}

	if(now==1)

		ans+=n%t+1;

	solve(t/10,s-1);

}

int main()

{

	scanf("%lld",&n);

	long long t=1;

	for(int i=1;i<=9;i++)

	{

		f[i]=i*t;

		t*=10;

	}

	t=1;

	long long s=1;

	while(t<n)	t*=10,s++;

	solve(t,s);

	printf("%lld",ans);

}

巴特西