dp 水平过于低下了，不能一天天琢磨分块了。
容斥原理
算法简介
一加一减一加一减，最后使得所有数恰好被加过一次。
Min-Max 容斥
超级优美的式子：
$Max(S)=\sum_{T\in S} (-1)^{|T|+1}\times Min(T)$
$Min(S)=\sum_{T\in S}(-1)^{|T|+1}\times Max(T)$
但是没用上过，该用的时候也不会ƪ(˘⌣˘)ʃ
硬币购物
dp+容斥计数。
首先可以观察到可以预先处理每种价值的方案数。
然后套上容斥的式子即可得到答案。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
int c[10],d[10];
int n,s;
ll f[N],ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
for(int i=1;i<=4;i++) cin>>c[i];
cin>>n;f[0]=1;
for(int i=1;i<=4;i++){
for(int j=c[i];j<=N-10;j++){
f[j]+=f[j-c[i]];
}
}
while(n--){
for(int i=1;i<=4;i++) cin>>d[i];
cin>>s;
ans=0;
for(int i=0;i<(1<<4);i++){
int tot=s,k=1;
for(int j=0;j<4;j++){
if((1<<j) & i){
k=-k;
tot-=(c[j+1]*(d[j+1]+1));
}
}
if(tot<0) continue;
ans+=f[tot]*k;
}
cout << ans << '\n';
}
return 0;
}
连续段 DP
耳朵龙学长说还没有学名，但是非常的强势。
算法简介
尝试把原序列按问题分成若干段，然后不考虑段内情况，只考虑段间的合并。
kangaroo
题目固定开头结尾，求生成一个波浪型的数列的方案数。
我们定义 $f_{i,j}$ 表示前 $i$ 个位置，一共分成 $j$ 段的方案数，要求段内合法。
考虑第 $i$ 个位置放在哪里然后分讨。具体看代码：
#include<bits/stdc++.h>
#define ll long long
#define p 1000000007
using namespace std;
const int N = 2e3+10;
int n,s,t;
ll f[N][N];
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
cin>>n>>s>>t;
f[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(i!=s && i!=t){
f[i][j]=(f[i][j]+j*f[i-1][j+1]%p+1ll*(j-(i>t)-(i>s))*f[i-1][j-1]%p)%p;
}else{
f[i][j]=(f[i-1][j-1]+f[i-1][j])%p;
}
}
}
cout << f[n][1]%p;
return 0;
}
斜率优化 DP
算法简介
将 dp 式子写成一次函数的形式，那么我们就可以进行斜率优化。
有些题的性质可以使用单调队列，但是李超树一定是万能的。
玩具装箱
转移方程形如：$f_i=\min(f_j+(s_i-s_j-l)^2)$ s 是前缀和。
设当前决策点是 $j_1$ 与 $j_2$，并且决策点 $j_2$ 更优。
划一划，把 $i$ 和 $j$ 分到两侧，然后就得到了：$2\times s_i \ge \dfrac{(f_{j_2}+(s_{j_2}+l)^2)-(f_{j_1}+(s_{j_1}+l)^2)}{s_{j_2}-s_{j_1}}$
令 $Y(j)=f_j+(s_j+l)^2,X(j)=s_j$，那么有 $2\times s_i\ge \dfrac{Y(j)-Y(i)}{X(j)-X(i)}$。
非常好的一次函数的形式，而且因为全部是单调的，所以可以拿单调队列直接维护.。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e4+10;
int n,l;
ll f[N],arr[N],que[N],head=1,tail;
inline ll X(ll i){return arr[i];}
inline ll Y(ll i){return f[i]+(arr[i]+l)*(arr[i]+l);}
inline ll d(ll i,ll j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>l;
for(int i=1,x;i<=n;i++){
cin>>x;arr[i]+=arr[i-1]+1+x;
}
que[++tail]=0;l++;
for(int i=1;i<=n;i++){
while(head<tail && d(que[head],que[head+1])<=2*arr[i]) head++;
int j=que[head];
f[i]=f[j]+(arr[i]-arr[j]-l)*(arr[i]-arr[j]-l);
while(head<tail && d(que[tail-1],que[tail])>=d(que[tail-1],i)) tail--;
que[++tail]=i;
}
cout << f[n];
return 0;
}
【模板】李超线段树
这个是维护斜率的宝具，超级无敌强大而且好写。不知道扔哪，就扔这吧。
首先我们需要一个储存线段的结构体：
struct Line{
double k,b;
int id;
Line(double _k=0,double _b=0,int _id=0):k(_k),b(_b),id(_id){}
double f(int x){
return k*x+b;
}
}tr[N];
然后我们需要一颗线段树，实现 线段覆盖 与 查询 $x$ 点的最大 $y$ 值所对应的线段编号 两个功能。
查询是 trivial 的，直接递归到对应叶子节点返回就行了。
重点在于线段覆盖，考虑以下三种情况，找两条线段中点进行比较：
- 新线段完全比老线段优：直接覆盖，交换编号即可。
- 新线段完全比老线段劣：直接舍弃，不管就行。
- 新线段部分比老线段优：将线段劈成两半，继续递归即可。
可以证明，复杂度最劣为 $O(\log^2 n)$。
bool cmp(Line x,Line y,int pos){
if(x.f(pos)-y.f(pos)>eps) return true;
if(y.f(pos)-x.f(pos)>eps) return false;
return x.id<y.id;
}
void upd(int u,int l,int r,Line s){
if(cmp(s,tr[u],mid)) swap(s,tr[u]);
if(cmp(s,tr[u],l)) upd(ls,l,mid,s);
if(cmp(s,tr[u],r)) upd(rs,mid+1,r,s);
}
void pushdown(int u,int l,int r){
if(!tr[u].id) return ;
upd(ls,l,mid,tr[u]);
upd(rs,mid+1,r,tr[u]);
tr[u]=Line();
}
int query(int u,int l,int r,int pos){
if(l==r) return tr[u].id;
pushdown(u,l,r);
if(pos<=mid) return query(ls,l,mid,pos);
else return query(rs,mid+1,r,pos);
}
void modify(int u,int l,int r,int x,int y,Line s){
if(l>=x && r<=y){
upd(u,l,r,s);return ;
}
pushdown(u,l,r);
if(x<=mid) modify(ls,l,mid,x,y,s);
if(mid<y) modify(rs,mid+1,r,x,y,s);
}
然后注意下 $k=0$ 的情况，特判掉就行。
#include<bits/stdc++.h>
#define ll long long
#define eps 1e-9
using namespace std;
const int N = 3e5+10;
const int M = 40000;
struct Line{
double k,b;
int id;
Line(double _k=0,double _b=0,int _id=0):k(_k),b(_b),id(_id){}
double f(int x){
return k*x+b;
}
}tr[N];
struct Tree{
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)
bool cmp(Line x,Line y,int pos){
if(x.f(pos)-y.f(pos)>eps) return true;
if(y.f(pos)-x.f(pos)>eps) return false;
return x.id<y.id;
}
void upd(int u,int l,int r,Line s){
if(cmp(s,tr[u],mid)) swap(s,tr[u]);
if(cmp(s,tr[u],l)) upd(ls,l,mid,s);
if(cmp(s,tr[u],r)) upd(rs,mid+1,r,s);
}
void pushdown(int u,int l,int r){
if(!tr[u].id) return ;
upd(ls,l,mid,tr[u]);
upd(rs,mid+1,r,tr[u]);
tr[u]=Line();
}
int query(int u,int l,int r,int pos){
if(l==r) return tr[u].id;
pushdown(u,l,r);
if(pos<=mid) return query(ls,l,mid,pos);
else return query(rs,mid+1,r,pos);
}
void modify(int u,int l,int r,int x,int y,Line s){
if(l>=x && r<=y){
upd(u,l,r,s);return ;
}
pushdown(u,l,r);
if(x<=mid) modify(ls,l,mid,x,y,s);
if(mid<y) modify(rs,mid+1,r,x,y,s);
}
}Tr;
int n,ans,tot;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1,op;i<=n;i++){
cin>>op;
if(op==0){
int pos;cin>>pos;
pos=(pos+ans-1)%39989+1;
ans=Tr.query(1,1,M,pos);
cout << ans << '\n';
}else{
int x,y,x0,y0;cin>>x>>y>>x0>>y0;
x=(x+ans-1)%39989+1;x0=(x0+ans-1)%39989+1;
y=(y+ans-1)%1000000000+1;y0=(y0+ans-1)%1000000000+1;
if(x>x0) swap(x,x0),swap(y,y0);
if(x==x0) Tr.modify(1,1,M,x,x0,Line(0,max(y,y0),++tot));
else{
double k=1.0*(y-y0)/(x-x0);
double b=y-k*x;
Tr.modify(1,1,M,x,x0,Line(k,b,++tot));
}
}
}
return 0;
}
非常的好写，感觉跟普通线段树区别不大。