[JOISC 2015 Day2] Keys

一、题目

点此看题

二、解法

把时间点排序，考虑每个时间段在什么条件下才会贡献，可以分成 \(4\) 种情况讨论（\(i\) 表示排序后这个点的人）：

• \(i\) 进 \(i+1\) 出，什么情况下都可以贡献。
• \(i\) 进 \(i+1\) 进，当且仅当 \(i+1\) 有钥匙才能开门，\(i\) 就会把门关上产生贡献。
• \(i\) 出 \(i+1\) 出，当且仅当 \(i\) 有钥匙才能关门，\(i\) 就会把门关上产生贡献。
• \(i\) 出 \(i+1\) 进，当且仅当两个人都有钥匙时 \(i\) 会在出去的时候把门关上，\(i+1\) 进来时能开门。
• \(\tt Otherwise\)，门都会保持打开的状态，所以有没有钥匙都一定能合法。

考虑计算贡献，贡献 \(1\) 直接记录到答案中，贡献 \(2,3\) 记录在需要钥匙的那个人上，也就是这个人有钥匙就能产生贡献。贡献 \(4\) 记录在两个人之间的边上，表示两个人都有钥匙就能产生贡献。

这样变成一张图上选点最大化贡献的问题，但是这个图有特殊限制，考虑每个点最多连出去两条边并且不会有环，所以这张图就是若干条链。我们把这条链的端点串起来，这样就变成了序列问题，就可以直接 \(dp\) 了，设 \(dp[i][j][0/1]\) 表示前 \(i\) 个点中分配了 \(j\) 把钥匙，第 \(i\) 个人有还是没有钥匙，时间复杂度 \(O(n^2)\)

三、总结

贡献法也能运用到规划问题中去，还是从小处入手，考虑贡献产生的条件即可，是无条件贡献？是点限制贡献？是边限制贡献？

#include 
#include 
using namespace std;
const int M = 4005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,t,w,ans,b[M],c[M],nxt[M],dp[2][M][M];
struct node
{
	int x,id,fl;
	bool operator < (const node &b) const
	{
		return x