「Test」不死的LYM

题意：你今天需要上 $n$ 节课，如果你在第 $i$ 堂课睡觉或不睡觉，减少和增加的疲劳度分别为 $down _{i},up _{i}$，你的初始疲劳值为 $s$，你给自己定下一个规矩：如果在某主科的课上睡了觉，那么下堂这科课就不能睡觉。$c _{i}$ 代表第 $i$ 节课的课程，只有 $c _{i}=7$ 时第 $i$ 节课才不为主科课。假设经过了这 $n$ 节课，你没有死，请问你对疲劳值的忍耐极限至少是多少(如果存在某节课后疲倦值)？

状压 DP。

设 $f _{i,j}$ 代表已经上完前 $i$ 节课，且 $j$ 状态中的科目目前不能再睡的最小疲劳值。

那么如果第 $i$ 节课不是主科，则我们选择直接睡，即 $f_ {i,j}=f_ {i-1,j}-down _{i}$。

如果第 $i$ 节课是主科，那么可以选择睡和不睡：

1. 如果我们选择睡，那么必须满足上次这节主科没睡，即 $j>>(c _{i}-1)\& 1=1$。

   $f _{i,j}=f _{i-1,j\ \text{xor}\ (1<<(c _{i}-1))}-down _{i}$；

2. 如果选择不睡，那么上节课睡不睡都没问题。

   $f _{i,j}=\min(f _{i-1,j}+up _{i},f _{i-1,j\ \text{xor}\ (1<<(c _{i}-1))+up _{i}})$。

   由于疲劳值超过了限度就会死，所以在转移时我们只有当疲劳值小于忍耐限度时才能转移。

但我们并不知道疲劳限度，怎么办？

二分答案！！

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=15010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,c[maxn],f[maxn][71];
int s,down[maxn],up[maxn];
int check(int limit)
{
	memset(f,0x3f,sizeof(f));
	f[0][0]=s;
	for(int i=1;i<=n;i++)
	{
		if(c[i]==7)
		{
			for(int j=0;j<=63;j++)
				if(f[i-1][j]<=limit)
					f[i][j]=min(f[i][j],f[i-1][j]-down[i]);
		}
		else
		{
			int t=1<<(c[i]-1);
			for(int j=0;j<=63;j++)
			{
				if((j>>(c[i]-1))&1)
				{
					if(f[i-1][j^t]<=limit)
						f[i][j]=min(f[i][j],f[i-1][j^t]-down[i]);
				}
				else
				{
					if(f[i-1][j]<=limit)
						f[i][j]=min(f[i][j],f[i-1][j]+up[i]);
					if(f[i-1][j^t]<=limit)
						f[i][j]=min(f[i][j],f[i-1][j^t]+up[i]);
				}
			}
		}
	}
	for(int i=0;i<=63;i++)
		if(f[n][i]<=limit)
			return true;
	return false;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&down[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&up[i]);
	scanf("%d",&s);
	int l=s,r=INF,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	printf("%d",l);
	return 0;
}