BZOJ 1046: [HAOI2007]上升序列

n^2的dp可过第一问

第二问只要从左往右贪心的取数就好了 只要当前的数的f[i]>l-top 且大于前一个数 就可以取来

千万要注意 题目中说的字典序最小是下标字典序最小而不是序列的字典序最小!!!!!!!

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=10010;
int f[N],s[N],n,m,q,ans[N],maxdp;
void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1046.in","r",stdin);freopen("1046.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(s[i]);s[0]=~0u>>1;
	for(int i=n;i>=1;i--){
		f[i]=1;
		for(int j=i+1;j<=n;j++) if(s[i]<s[j]) f[i]=max(f[i],f[j]+1);
		maxdp=max(maxdp,f[i]);
	}
	read(m);
	while(m--){
		int l;
		read(l);
		if(maxdp>=l){
			int top=0;
			ans[0]=-(~0u>>1);
			for(int i=1;i<=n;i++) if(l-f[i]<=top && s[i]>ans[top]) ans[++top]=s[i];
			for(int i=1;i<l;i++) printf("%d ",ans[i]);printf("%d\n",ans[l]);
		}
		else printf("Impossible\n");
	}
	return 0;
}

BZOJ 1096: [ZJOI2007]仓库建设

推dp方程

首先将所有的工厂按距离排序

定义f[i]表示前i个工厂的所有货都能够保存下来的最小费用,cost[i][j]为把所有i到j的货物运到j的费用,那么显然

$f[i]=min{ f[j]+cost[j+1][i]+c[i]} (0\leq j \leq i-1)$

考虑如何计算cost[i][j],定义sum[i]表示前i个工厂的物品个数之和,d[i]表示工厂i到第一个工厂的距离 那么可以得到

$cost[i][j]=cost[1][j]-cost[1][i]-sum[j]*(d[j]-d[i])$

于是只要预处理出cost[1][i]和sum[i]就可以O(1)计算cost[i][j]。下面用cost[i]表示cost[1][i]

看到n这么大,我们试一试斜率优化

假设j>k,且决策j比k优

那么有

$f[j]+cost[i]-cost[j]-sum[j]*(d[i]-d[j])+c[i] < f[k]+cost[i]-cost[k]-sum[k]*(d[i]-d[k])+c[i]$

将所有有关i的移项到右边其他移到左边可以得到

$(f[j]-cost[j])-(f[k]-cost[k])+sum[j]*d[j]-sum[k]*d[k] < d[i]*(sum[j]-sum[k])$

由于sum[j]>sum[k],可以除过来,否则要考虑不等号变向问题 则

$\frac{(f[j]-cost[j])-(f[k]-cost[k])+sum[j]*d[j]-sum[k]*d[k]}{(sum[j]-sum[k])} < d[i]$ d[i]递增可以斜率优化

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1000010;
struct Fact{LL c,d,p;}fa[N];
LL n,cost[N],f[N],sum[N],q[N*3],l,r;
bool cmp(Fact a,Fact b){return a.d<b.d;}
double slop(int k,int j){return (f[j]-cost[j]-(f[k]-cost[k])+sum[j]*fa[j].d-sum[k]*fa[k].d)/(double)(sum[j]-sum[k]);}
void read(LL &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1096.in","r",stdin);freopen("1096.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(fa[i].d),read(fa[i].p),read(fa[i].c);
	sort(fa+1,fa+n+1,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+fa[i].p,cost[i]=cost[i-1]+sum[i-1]*(fa[i].d-fa[i-1].d);
	for(int i=1;i<=n;i++){
		while(l<r && slop(q[l],q[l+1])<fa[i].d) l++;
		int j=q[l];
		f[i]=f[j]+cost[i]-cost[j]-sum[j]*(fa[i].d-fa[j].d)+fa[i].c;
		while(l<r && slop(q[r-1],q[r])>slop(q[r],i)) r--;
		q[++r]=i;
	}
	printf("%lld",f[n]);
	return 0;
}

BZOJ 2748 [HAOI2012]音量调节

看起来是个傻逼题

定义f[i][j]表示第i个节目音量能否为j ,则f[i][j]= f[i-1][j+c[i]] || f[i-1][j-c[i]]。最后扫一下f[n]里面的最大值

滚动数组都不用开就过了

 代码

#include <cstdio>
#include <algorithm>
using namespace std;
int n,bl,ml,a[55],ans=0;
bool f[55][1010];
int main(){
	// freopen("2748.in","r",stdin);freopen("2748.out","w",stdout);
	scanf("%d%d%d",&n,&bl,&ml);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[0][bl]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=ml;j++) {
			if(j-a[i]>=0 && f[i-1][j-a[i]]) f[i][j]=1;
			if(j+a[i]<=ml && f[i-1][j+a[i]]) f[i][j]=1;
		}
	for(int i=ml;i>=0;i--) if(f[n][i]) {printf("%d",i);ans=1;break;}
	if(!ans) printf("-1");
	return 0;
}

BZOJ 1009 [HNOI 2008] GT考试

这题本来第一个反应是数位dp 然而看到n这么大- - 管他呢照样数位dp 矩阵快速幂优化一下就好了

这道题的关键 是 利用kmp算法 构建转移矩阵

定义f[i][j]表示 i位的数字的最后j位 和不吉利数字的开始j位相同 的方案数有多少,然后我们就开始想转移方程,然而 这转移不是和给出的数字串有关吗……(其实我本来以为是f[i][j]=f[i-1][j-1]+9*f[i-1][j+1]的,打好之后发现样例都过不去……) 。既然字符串给出了 那我们一定可以用奇技淫巧弄出转移的方程 ——对就是kmp

我们用kmp算法匹配的时候 是不断的用fail指针跳转 直到匹配成功为止 在这里我们用相同的方法处理

对于某一个匹配长度k,我们枚举这个位置的数字i 然后进行匹配 fail指针不断的回跳 直到匹配成功或者跳出了字符串 这时候 我们就知道 匹配长度为k的字符串 在添加一个数字i之后 可以转移到哪个位置,转移矩阵中的对应位置++即可。这样就构造成功了转移矩阵,接下来就是用矩阵快速幂随便搞一下,把f[n][0]到f[n][m-1]加起来模一下就是答案了

代码

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,mod,s[30],f[30],nxt[30],sum;
struct mat{
	int a[30][30];
	void reset(){for(int i=0;i<30;i++) for(int j=0;j<30;j++) a[i][j]=0;}
	void set1(){reset();for(int i=0;i<=29;i++) a[i][i]=1;}
	friend mat operator *(mat x,mat y){
		mat z;
		z.reset();
		for(int i=0;i<=20;i++)
			for(int j=0;j<=20;j++)
				for(int k=0;k<=20;k++) (z.a[i][j]+=x.a[i][k]*y.a[k][j])%=mod;
		return z;
	}
}st,zy,ans;
void get(){
	int p;
	f[0]=0;f[1]=0;
	for(int i=2;i<=m;i++) {
		p=f[i-1];
		while(s[p]!=s[i-1] && p) p=f[p];
		f[i]= s[p]==s[i-1]?p+1:0;
	}
	for(int i=0;i<m;i++)
		for(int j=0;j<=9;j++) {
			if(j==s[i]) {zy.a[i][i+1]++;continue;}
			int p=f[i];
			while(s[p]!=j && p) p=f[p];
			if(s[p]==j) zy.a[i][p+1]++;else zy.a[i][0]++;
		}
}
int main(){
	//freopen("1009.in","r",stdin);freopen("1009.out","w",stdout);
	scanf("%d%d%d\n",&n,&m,&mod);
	for(int i=0;i<m;i++) s[i]=getchar()-'0';
	get();
	ans.set1();
	st.a[0][0]=1;
	for(;n;n>>=1){if(n&1)ans=ans*zy;zy=zy*zy;}
	st=st*ans;
	for(int i=0;i<m;i++) (sum+=st.a[0][i])%=mod;
	printf("%d",sum);
	return 0;
}

Vijos P1037 解题报告

阅读全文