密室逃脫

題解

簡單dp

其實看到這道題是很容易想到dp的誰知道我當時哪里打錯了，
我們先令 d p i , j dp_{i,j} dpi,j?表示當第 i i i個點有 j j j個人時，前 i i i個點的最多人數，
轉移方程式其實挺容易想的，

• 若 j < a i j< a_{i} j<ai?，那么有 f i + 1 , j + b i = max ? ( f i , j + b i ) f_{i+1,j+b_{i}}=\max(f_{i,j}+b_{i}) fi+1,j+bi??=max(fi,j?+bi?)， f i + 1 , k = max ? ( f i , j + j ) [ k ∈ [ 0 , b i ) ] f_{i+1,k}=\max(f_{i,j}+j)[k\in [0,b_{i})] fi+1,k?=max(fi,j?+j)[k∈[0,bi?)]
  對應的是該點從后面來與與后面隔絕兩種情況，
• 若 a i ? j < a i + b i a_{i}\leqslant j< a_{i}+b_{i} ai??j<ai?+bi?，那么有 f j ? a i = max ? ( f i , j ) f_{j-a_{i}}=\max(f_{i,j}) fj?ai??=max(fi,j?)，
  對應的是后面的點從前面來的情況，
• 若 a i + b i ? j a_i+b_i\leqslant j ai?+bi??j，那么 f i + 1 , j = f i , j f_{i+1,j}=f_{i,j} fi+1,j?=fi,j?，因為這種情況下一定可以雙方通行了~~，話‘說前兩種好像是一方通行~~，

其實也很容易理解，最后的情況一定每一個房間有固定的人數，保證通行，它們無法到房間1，其它人全在第一個房間，
然后跑一遍dp就可以了，

時間復雜度 O ( n max ? ( m , a + b ) ) O\left(n\max(m,a+b)\right) O(nmax(m,a+b))，

原始碼

我也不知道為什么我如果直接對 d p i , j dp_{i,j} dpi,j?求它從哪里轉移過來會WA，

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define MAXN 1005
#define MAXM 40005
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
typedef unsigned long long uLL;
typedef unsigned int uint;
typedef pair<int,int> pii;
const int INF=0x7f7f7f7f;
const int mo=1e9+7;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
int n,m,a[MAXN],b[MAXN],sum,f[MAXM],g[MAXM],maxx;bool flag;
bool check(int mid){int sum=mid;for(int i=n;i>1;i--){sum-=a[i];if(sum>=b[i])sum+=a[i];}return sum<m;}
int solve(){int l=0,r=1e8;while(l<r){int mid=l+r+1>>1;if(check(mid))l=mid;else r=mid-1;}return l;}
signed main(){
	freopen("escape.in","r",stdin);
	freopen("escape.out","w",stdout);
	read(n);read(m);int ans=m-1;
	for(int i=1;i<n;i++)read(a[i]),read(b[i]),flag|=(a[i]!=1||b[i]!=1),maxx=max(maxx,a[i]+b[i]);
	if(!flag){printf("%d\n",max((n-(m==1)+1)/2,m-1));return 0;}
	for(int i=0;i<m;i++)g[i]=i;for(int i=m;i<=maxx;i++)g[i]=-INF;
	for(int i=0;i<=maxx;i++)f[i]=-INF;
	for(int i=1;i<n;i++){
		int tmp=0;
		for(int j=0;j<=maxx;j++){
			if(j<a[i]&&j+b[i]<=maxx)f[j+b[i]]=max(f[j+b[i]],g[j]+b[i]);
			if(a[i]<=j&&j<a[i]+b[i])f[j-a[i]]=max(f[j-a[i]],g[j]);
			if(a[i]+b[i]<=j)f[j]=max(f[j],g[j]);if(j<a[i])tmp=max(tmp,g[j]);
		}
		for(int j=0;j<b[i];j++)f[j]=max(f[j],tmp+j);
		for(int j=0;j<=maxx;j++)g[j]=f[j],f[j]=-INF;
	for(int i=0;i<=maxx;i++)ans=max(ans,g[i]);printf("%d\n",ans);
	return 0;
}

謝謝！！！