Free Market
https://www.luogu.com.cn/problem/CF364B
一个观察是第一个限制是无用的，原因在于你拿去的如果跟它有交你就只换没交的部分就行了。所以你手上一个总权值为 X 的状态，是可以换任意一个总权值为 [X+1,X+d] 的状态的。你可以把所有可达状态用 01 背包预处理出来（注意循环顺序），然后就是按刚才说的跳就行了，直到跳不了为止。
#include <bits/stdc++.h>
using namespace std;
const int N=6e5+5;
int n,d;
bool f[N];
int main(){
ios::sync_with_stdio(0);
cin>>n>>d;
f[0]=1;
for(int i=1,x,s=0;i<=n;i++){
cin>>x,s+=x;
for(int j=s;j>=x;j--)f[j]|=f[j-x];
}
int day=0,now=0;
while(1){
bool fl=0;
for(int i=now+d;i>now;i--)if(f[i]){now=i;fl=1;break;}
if(!fl)break;
day++;
}
cout<<now<<' '<<day;
}
Hills
https://www.luogu.com.cn/problem/CF1012C
作为练习题非常合适，若能自己推出来该多有成就感（话说CF评级咋这么低）。ouuan 题解的思路历程耐人寻味。
#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int n,a[N],f[2][N][3];
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
memset(f[0],0x3f,sizeof f[0]),f[0][0][0]=f[0][0][2]=0;
for(int i=1,o=1;i<=n;i++,o^=1){
memset(f[o],0x3f,sizeof f[o]);
for(int j=0;j<=i;j++){
f[o][j][0]=min(f[o^1][j][0],f[o^1][j][2]);
if(j)f[o][j][1]=min(f[o^1][j-1][0]+max(0,a[i-1]-a[i]+1),f[o^1][j-1][2]+max(0,min(a[i-1],(i==1?1000000000:a[i-2])-1)-a[i]+1));
f[o][j][2]=f[o^1][j][1]+max(0,a[i]-a[i-1]+1);
}
//cout<<f[1][][0];
}
for(int i=1;i<=(n+1)/2;i++)cout<<min({f[n&1][i][0],f[n&1][i][1],f[n&1][i][2]})<<' ';
}
Polygon
https://www.luogu.com.cn/problem/CF1572E
最小值最大，必然是二分答案。多边形剖分，必然是区间 dp。
如何将上面两件事情有机结合在一起是本题难点。事实上，我们希望在每一块儿都 \(\ge mid\) 的情况下，块的数量最大。可以就 dp 这个块的数量，这很显然。但是会不好转移，主要矛盾就出在这儿：不足 mid 的块丢哪儿？我们可以用另一个数组附带记录现在总共有多少面积的 leftover，那么一旦区间 dp 时我们 [l,k] 和 [k,r] 的 leftover 再加上 \(S_{\triangle P_lP_kP_r}\) 加起来 \(\ge mid\) 了，我们就贪心把它合并，leftover 设 0。顺利解决。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205;
int n,K;
pair<int,ll>f[N][N];
struct P{int x,y;}a[N];
ll S(P a,P b,P c){
return abs(1ll*(a.x-b.x)*(c.y-b.y)-1ll*(c.x-b.x)*(a.y-b.y));
}
bool check(ll mid){
for(int len=3;len<=n;len++)for(int l=1,r=len;r<=n;l++,r++){
f[l][r]=make_pair(0,0);
for(int k=l+1;k<r;k++){
ll t=S(a[l],a[k],a[r]);
if(t+f[l][k].second+f[k][r].second>=mid)f[l][r]=max(f[l][r],make_pair(f[l][k].first+f[k][r].first+1,0ll));
else f[l][r]=max(f[l][r],make_pair(f[l][k].first+f[k][r].first,f[l][k].second+f[k][r].second+t));
}
}
return f[1][n].first>=K+1;
}
int main(){
cin>>n>>K;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
ll L=0,R=80000000000000007,mid;//不可写8e16+7，具体见luogu.com.cn/blog/300078/cuo-ti-ji 第83条
while(L<R-1){
mid=L+R>>1;
if(check(mid))L=mid;
else R=mid;
}
cout<<L;
}
AND Segments
https://www.luogu.com.cn/problem/CF1327F
非常经典的 dp 题。
- 对象为区间的 dp 基本解决方案是框定完全属于某子结构（子区间、前缀等）的所有区间作为子问题，另一部分是跨越两个子结构的区间的信息的利用。
- 本题中，显然按位考虑，就变成序列上有些位置已经是 1，固定了，决定每个其他位置放 0 还是放 1，要满足第二类区间的限制，合法方案数。0 的分布显然是问题关键；而“分布”的微观就是“该位置选不选”。
由此二可设状态 \(f(i)\) 表示完全包含于前缀 \(i\) 的第二类区间都满足条件，钦定 \(i\) 放 0，则前缀 \(i\) 中候选位置的方案数。（此时 \(i\) 必须是一个候选位置。）从前一个 \(0\) 所在位置转移，那么这个位置 \(j\) 应该满足：不存在一个右端点 \(<i\) 的第二类区间，它的左端点 \(>j\)。换句话说，所有右端点 \(<i\) 的区间的左端点的最大值就是 \(j\) 最小能取的位置。\(\sum f(j)\) 即为 \(f(i)\)。每位的 \(f(n+1)\) 乘起来即可。
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5,mod=998244353;
inline int read(){
register char ch=getchar();register int x=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
inline void Add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
int n,K,m,tot,f[N],b[N];
struct ran{int l,r;}a[N];
struct initran{int l,r,x;}aa[N];
int solve(){
int maxl=0,sum=0,all=1;
f[0]=1;
for(int i=1,j=1,k=0;i<=n+1;i++){
b[i]+=b[i-1];
while(j<=tot&&a[j].r<i)maxl=max(maxl,a[j].l),j++;
while(k<maxl)Add(sum,f[k++]);
if(!b[i])f[i]=(all-sum+mod)%mod;
else f[i]=0;
Add(all,f[i]);
}
return f[n+1];
}
int main(){
n=read(),K=read(),m=read();
for(int i=1;i<=m;i++)aa[i].l=read(),aa[i].r=read(),aa[i].x=read();
sort(aa+1,aa+m+1,[](initran a,initran b){return a.r<b.r;});
int ans=1;
for(int i=0;i<K;i++){
tot=0;
for(int j=1;j<=n+1;j++)b[j]=0;
for(int j=1;j<=m;j++){
if(aa[j].x>>i&1){
b[aa[j].l]++,b[aa[j].r+1]--;
}
else {
a[++tot].l=aa[j].l,a[tot].r=aa[j].r;
}
}
ans=1ll*ans*solve()%mod;
}
cout<<ans;
}
On the Bench
https://www.luogu.com.cn/problem/CF840C
https://www.luogu.com.cn/blog/300078/solution-cf840c
Amusement Park
https://www.luogu.com.cn/problem/P6846
首先观察到一个合法方案中将每条边反向的方案一定还是一个合法方案，所以最终答案应该是 \(\frac m2\cdot 方案数\)。
显然状压，但是怎么转移呢？我在讨论区提问无人解答，那就姑且记作：
无向图的定向问题的解决方法是：状压 dp 转移时枚举子集（要求是独立集，可 \(=S\)）\(T\) 作为第一层，然后用 \(f(S)=\sum (-1)^{|T|-1}f(S-T)\) 转移。\(f(0)=1\)。 有容斥系数是因为发现肯定会算重，容斥系数想破头都想不出来的话可以手推小数据找规律。
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
inline void add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
int n,m,f[1<<18],p[1<<18],e[20][20];
bool is[1<<18];
int main(){
cin>>n>>m;
for(int i=1,u,v;i<=m;i++)cin>>u>>v,e[u][v]=e[v][u]=1;
f[0]=1;
for(int s=1;s<(1<<n);s++){
p[s]=__builtin_popcount(s);
is[s]=1;
for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(e[i][j]&&(s>>(i-1)&1)&&(s>>(j-1)&1)){is[s]=0;break;}
if(p[s]==1){f[s]=1;continue;}
for(int t=s;t;t=(t-1)&s)if(is[t])add(f[s],((p[t]&1)?f[s-t]:mod-f[s-t]));
}
cout<<(mod+1ll)/2*f[(1<<n)-1]%mod*m%mod;
}
Kuro and Topological Party
太晚了，我就拷贝最高赞题解吧，这是一个 \(O(n)\)(?!!)的做法。
套路一下，把点分为偶黑,偶白,奇黑,奇白四类。（比如说，奇白代表有奇数条路径以该点为结尾且该点为白色）
考虑加入一个白色点 i ，我们讨论一下
连到偶黑，路径条数加上一个偶数，奇偶性不变。
连到偶白和奇白，不是黑白相间的路径，路径条数奇偶性不变。
下面讨论一下奇黑的情况
存在奇黑，我们可以挑出一个奇黑点来控制奇偶性，即这个白点作为奇白和偶白的方案数各为\(2^{i-2}\)；（编者按：你可以手推发现具体有多少个奇黑都不影响\(2^i\)中选法对半分）
不存在奇黑，它自己算一条黑白相间的路径，只能作为奇白
至此，加入白色点的讨论就结束了。
黑色自行分析
#include <bits/stdc++.h>
using namespace std;
const int N=55,mod=1e9+7;
inline void add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
int n,jerry,a[N],f[N][2][2][2];
long long _2[N];
int main(){
cin>>n>>jerry;
_2[0]=1;
for(int i=1;i<=n;i++)cin>>a[i],_2[i]=_2[i-1]*2%mod;
f[0][0][0][0]=1;
for(int i=0;i<n;i++)for(int pyl=0;pyl<=1;pyl++)
for(int jibai=0;jibai<=1;jibai++)for(int jihei=0;jihei<=1;jihei++){
if(!f[i][pyl][jibai][jihei])continue;
if(a[i+1]==-1||a[i+1]==0){
if(jihei)add(f[i+1][!pyl][jibai|1][jihei],f[i][pyl][jibai][jihei]*_2[i-1]%mod),
add(f[i+1][pyl][jibai][jihei],f[i][pyl][jibai][jihei]*_2[i-1]%mod);
else add(f[i+1][!pyl][jibai|1][jihei],f[i][pyl][jibai][jihei]*_2[i]%mod);
}
if(a[i+1]==-1||a[i+1]==1){
if(jibai)add(f[i+1][!pyl][jibai][jihei|1],f[i][pyl][jibai][jihei]*_2[i-1]%mod),
add(f[i+1][pyl][jibai][jihei],f[i][pyl][jibai][jihei]*_2[i-1]%mod);
else add(f[i+1][!pyl][jibai][jihei|1],f[i][pyl][jibai][jihei]*_2[i]%mod);
}
}
cout<<((long long)f[n][jerry][0][0]+f[n][jerry][0][1]+f[n][jerry][1][0]+f[n][jerry][1][1])%mod;
}
Tree Elimination
Fox and Hunting
Shrinking Tree
原文地址：http://www.cnblogs.com/impyl/p/16823382.html
