题解 [USACO14DEC]Guard Mark G

分析

看到数据范围就直接想状压。对于每一种状态，它的高度是一定的，你更改上下次序只会影响上面还能放多少重量，所以用 \(H[i]\) 预处理 \(i\) 这个状态总高度多少，用 \(f[i]\) 表示 \(i\) 这个状态最多上面还能放多少重量，转移应是新放的牛的承重量和被转移的 \(f\) 值减去该牛重量，最后找答案时，取最大的满足 \(H[i]\) 大于等于所需高度的 \(i\) 的 \(f[i]\) 就行了。

代码

#include 
using namespace std;
inline void read(int &res){
	res=0;
	int f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')res=(res<<1)+(res<<3)+c-48,c=getchar();
	res*=f;
}
int n,m;
int N;
int h[25],w[25],s[25];
int f[1100005];
int H[1100005];
int zy[25];
signed main()
{
	read(n);read(m);
	N=(1<=m&&f[i]>=0){
			ans=max(ans,f[i]);
		}
	}
	if(ans<0)puts("Mark is too tall");
	else cout<