[JZOJ3521]道路覆盖--状压DP

题目链接

略略略

分析

首先一看到使得最低的高度最高就想到了二分,于是就转化成了一个是否可行的问题

发现这个\(k\)都很小,考虑使用状态压缩DP

但是我一开始发现似乎并不好设计状态...如果这个\(k\)表示前\(k\)个方块的状态有没有开始涂似乎不好转移

看了solution发现我还是\(Too Young Too Simple\)

我们用对于第\(i\)块,对它决策有影响的只有它前面的\(i-k+1\)块的状态,于是我们只需要用一个\(k\)位二进制串表示状态来从\(i\)递推到\(i+1\).对于块\(p\)二进制串的第\(i\)位(0位开始)表示第\(p-(k-i-1)\)块的状态

\(f[i][s]\)表示已经从前往后决策完第\(i\)块,\(i-k+1\)到\(i\)的状态为\(s\)的最小代价,这些状态保证都是合法的(即所有的高度等于等于二分值)

这时候从\(i\)递推到\(i+1\)的话我们需要知道之前\(i+1\)之前\(k\)块能累高\(i+1\)块多少高度,这直接扫一遍就好了

如果之前累加的高度\(dta\)+\(h[i+1]\)大于等于二分的高度,那么我们可以不选涂第\(i+1\)块

\(f[i+1][s>>1]=min(f[i+1][s>>1],f[i][s])\),这时候第\(k-1\)位为0表示\(i+1\)位没涂

如果\(dta+h[i+1]+e[i+1]\)大于等于二分值,那么我们就可以涂

\(f[i+1][s>>1|(1<<(k-1))]=min(f[i+1][s>>1|(1<<(k-1))],f[i][s]+c[i+1])\)

意义和第一个类似表示\(i+1\)位涂的状态

最后判断是否有状态\(f[n][s]<=m\)就好了

感觉这题还是挺不错的,通过考虑那些状态会影响决策来减小决策空间,表示状态的方法也比较独特(可能是我太菜做的题少)

同时从大佬代码中学到了一个优化就是可行性剪枝,对于\(f[i][s]\)已经大于等于\(m\)的我们直接不管

代码

/*

  code by RyeCatcher

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <utility>

#include <queue>

#include <vector>

#include <ext/pb_ds/hash_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

#include <iostream>

#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define ri register int

#define ll long long

#define ull unsigned long long

#define SIZE 1<<22

using std::min;

using std::max;

using std::priority_queue;

using std::queue;

using std::vector;

using std::pair;

using namespace __gnu_pbds;

inline char gc(){

    static char buf[SIZE],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;

    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;

}

const int maxn=1005;

const int inf=0x7fffffff-1926817;

int f[maxn][1<<11];

int S,n,m,k;

int h[maxn],c[maxn],e[maxn];

inline  bool chk(int qwq){

	for(ri i=0;i<=n;i++)for(ri j=0;j<S;j++)f[i][j]=inf;

	f[0][0]=0;

	int num=0;

	for(ri o=0;o<n;o++){

		for(ri i=0;i<S;i++){

			if(f[o][i]>m)continue;//优化

			num=0;

			for(ri j=1;j<k;j++){

				if(o-(k-j)+1<=0)continue;

				if(i&(1<<j))num+=e[o-(k-j)+1];

			}

			if(num+h[o+1]>=qwq){

				f[o+1][i>>1]=min(f[o+1][i>>1],f[o][i]);

			}

			if(num+h[o+1]+e[o+1]>=qwq){

				f[o+1][i>>1|(1<<(k-1))]=min(f[o+1][i>>1|(1<<(k-1))],f[o][i]+c[o+1]);

			}

		}

	}

	for(ri j=0;j<S;j++)if(f[n][j]<=m)return 1;

	return 0;

}

int main(){

	int ans=0;

	FO(cover)

	read(n),read(m),read(k);

	for(ri i=1;i<=n;i++){

		read(h[i]),read(e[i]),read(c[i]);

	}

	S=1<<k;

	int mid,L=0,R=1e6+5;

	while(L<=R){

		mid=(L+R)>>1;

		if(chk(mid))ans=mid,L=mid+1;

		else R=mid-1;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

[JZOJ3521]道路覆盖--状压DP

题目链接

分析

代码

最新文章

热门文章