插入Dp

,

一种 dp trick

常常在算贡献时，与排列相邻两个数的相对大小有关。这时候我们将排列从小到大插入，状态为有几个连着的“块”。分新建块，插入块头快尾，合并块。

常常要讨论转移的合法性。

[CEOI2016] kangaroo

令 $f[i][j]$ 表示已经插入前 $i$ 个数，共有 $j$ 个块。

先不考虑头尾的限制。

  • 新建块，可以建在 $j$ 个空隙中，$f[i][j]+=f[i-1][j-1]\times j$。如果头尾已经填了，那么最头上和最后面都不能新建。
  • 合并块，从 $f[i][j+1]$ 转移过来，有 $j$ 个可以合并的空隙。$f[i][j]+=f[i-1][j+1]*j$

头尾特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 2005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int f[maxn][maxn];
const int mod=1e9+7;
signed main(void){
	int i,j,n,s,t;
	read(n);read(s);read(t);
	f[0][0]=1;
	for (i=1;i<=n;i++) {
		for (j=1;j<=i;j++){
			if (i==s||i==t) f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
			else f[i][j]=((j-(i>s)-(i>t))*f[i-1][j-1]+j*f[i-1][j+1])%mod;
		}
	}
	printf("%lld",f[n][1]);
	return 0;
}

CF704B Ant Man

首先将 $a+=x,b-=x,c+=x,d-=x$

分三种情况：新建、插入、合并情况讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 5005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int a[maxn],b[maxn],c[maxn],d[maxn];
int f[maxn][maxn],s,t,n,e[maxn]; 
signed main(void){
	int i,j,x;
	memset(f,0x3f,sizeof(f));
	read(n);read(s);read(t);
	for (i=1;i<=n;i++) read(e[i]);
	for (i=1;i<=n;i++) read(a[i]);
	for (i=1;i<=n;i++) read(b[i]);
	for (i=1;i<=n;i++) read(c[i]);
	for (i=1;i<=n;i++) read(d[i]);
	for (i=1;i<=n;i++) {
		x=e[i];
		c[i]+=x;b[i]-=x;a[i]+=x;d[i]-=x;
	}
	f[0][0]=0;
	for (i=1;i<=n;i++) {
		for (j=1;j<=i;j++) {
			if (i==s) {
				if (j>(i>s)) f[i][j]=min(f[i][j],f[i-1][j-1]+d[i]);
				f[i][j]=min(f[i][j],f[i-1][j]+c[i]);
			}
			else if (i==t) {
				if (j>(i>t)) f[i][j]=min(f[i][j],f[i-1][j-1]+b[i]);
				f[i][j]=min(f[i][j],f[i-1][j]+a[i]);
			}
			else {
				if (j>(i>t)+(i>s)) f[i][j]=min(f[i][j],f[i-1][j-1]+b[i]+d[i]);//记得判断
				if (j>(i>t)) f[i][j]=min(f[i][j],f[i-1][j]+a[i]+d[i]);
				if (j>(i>s)) f[i][j]=min(f[i][j],f[i-1][j]+b[i]+c[i]);
				f[i][j]=min(f[i][j],f[i-1][j+1]+a[i]+c[i]);
			}
		}
	}
//	gdb(f[1][1],f[2][1]);
	printf("%lld",f[n][1]);
	return 0;
}

CF1515E Phoenix and Computers

有插入 dp 的 $O(n^2)$ 做法。