【训练】算法竞赛进阶指南-5动态规划

本处难度分档以个人实力为参照系
难度1:半小时内想出,半小时内ac
难度2:半小时想不出,看题解,服气
难度3:半小时想不出,看题解,ac后依然觉得难度很大

另外,由于追进度,对于coding部分比较有自信的题目,不再具体实现

0x50 动态规划

部分题目

1 5101 LCIS

8.22 难度2

请先思考后再展开

精妙的做法
设 $f(i,j)$ 表示以b[j]结尾,匹配到i的最长LCIS
$a_i \neq b_j,f(i,j)=f(i-1,j)$
$a_i=b_j,f(i,j)=max_{0<k<j,b_k<b_j} f(i-1,k)+1$
$a_i=b_j,f(i,j)=max_{0<k<j,b_k<a_i} f(i-1,k)+1$
乍一看是$n^3$级别的,但其实k的位置是可以动态维护的

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
const int MAXN=3100;
int mymax(int x,int y) {return x>y?x:y;}
int a[MAXN],b[MAXN];
int f[MAXN][MAXN];
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
{
int k=0;//0<k<j
for(int j=1;j<=n;j++)
{
if(a[i]!=b[j]) f[i][j]=f[i-1][j];
else f[i][j]=f[i-1][k]+1;
if(b[j]<a[i] and f[i-1][j]>f[i-1][k]) k=j;
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=mymax(ans,f[n][i]);
printf("%d",ans);
}
};
int main()
{
mine::main();
}

2 5105 Cookies

8.22 难度2

请先思考后再展开

好题
对于决策的分配,可以从等效状态直接转移
抓住【排序后分配额递减】和【饼干至少1】的特性
同时怒气值是根据相对大小产生的,所以可以整体少1
设 $f(i,j)$ 表示给前i个人j块饼干的花费

决策1,所有人减少1块(当$j-i \geq i$)
$$f(i,j)=f(i,j-i)$$
决策2,后k个人(包括i)都是1块
$$f(i,j)=min_{k=1}^{i-1} { f(i-k,j-k) + (i-k) \times \sum_{t=i-k+1}^i g[t] }$$

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=40,MAX_M=5100;
int g[MAX_N];
ll s[MAX_N];//前缀和
int pos[MAX_N];
bool cmp(int x,int y) {return g[x]>g[y];}
ll f[MAX_N][MAX_M];
int fm[MAX_N][MAX_M];
int n,m;
int ans[MAX_N];
void output(int a,int b)
{
if(a==0 and b==0) return;
int k=fm[a][b];
if(k==0)
{
output(a,b-a);
for(int i=1;i<=n;i++) ans[pos[i]]++;
}
else
{
output(a-k,b-k);
for(int i=a-k+1;i<=a;i++) ans[pos[i]]=1;
}
}
void main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&g[i]),pos[i]=i;
sort(pos+1,pos+n+1,cmp);
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+g[pos[i]];
for(int j=i;j<=m;j++)
{
if(j-i>=i) f[i][j]=f[i][j-i],fm[i][j]=0;
for(int k=1;k<=i;k++)
{
ll nx=f[i-k][j-k]+ll(i-k)*(s[i]-s[i-k+1-1]);
if(f[i][j]>nx) f[i][j]=nx,fm[i][j]=k;
}
}
}
printf("%lld\n",f[n][m]);
output(n,m);
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
}
};
int main()
{
mine::main();
}

3 poj1015 Jury Compromise

8.22 难度2

请先思考后再展开

把差值作为体积,和作为权值,跑背包
难点在于回溯
刚开始在外层跑第几个物品,然后发现会出现一种情况,即使倒着枚举已选数量:
现在使用过的物品,可能把当前依赖的那个位置给更新掉,不符合01背包
所以改成在里面枚举,这样每次强行判断一下就好了
如果要稍微降低代码复杂度,同时剪剪枝(其实也就是20),可以考虑刷表法

话说跟风akc,第一次用宏
对于这道题是真的爽

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=210,MAX_M=30;
int mymax(int x,int y) {return x>y?x:y;}
#define f(i,j) F[i][550+(j)]
#define fm(i,j) Fm[i][550+(j)]
int F[MAX_M][1100];
int Fm[MAX_M][1100];
int h[MAX_N],w[MAX_N];
int person[MAX_M];
void main()
{
int ct=0;
while(1)
{
int n,m;scanf("%d%d",&n,&m);
if(n==0 and m==0) break;
printf("Jury #%d\n",++ct);
for(int i=1;i<=n;i++)
{
int x,y;scanf("%d%d",&x,&y);
h[i]=x-y;w[i]=x+y;
}
memset(F,-1,sizeof F);
f(0,0)=0;
for(int i=0;i<=m-1;i++)
for(int val=-500;val<=500;val++) if(f(i,val)>=0)//刷表法更方便
for(int k=1;k<=n;k++)
if(f(i+1,val+h[k])<f(i,val)+w[k])//剪枝
{
bool bk=0;
int a=i,b=val;
while(a!=0)
{
int t=fm(a,b);
if(t==k) {bk=1;break;}
a--;b-=h[t];
}
if(bk) continue;//判重
f(i+1,val+h[k])=f(i,val)+w[k];
fm(i+1,val+h[k])=k;
}
int v;
for(int val=0;val<=500;val++)
{
if(f(m,-val)>=f(m,val) and f(m,-val)>=0) {v=-val;break;}
if(f(m,val)>=f(m,-val) and f(m,val)>=0) {v=val;break;}
}
int p=0,d=0;
int now=m;
while(now>0)
{
int k=fm(now,v);
person[now]=k;
p+=(h[k]+w[k])/2;d+=(w[k]-h[k])/2;
now--;v-=h[k];
}
sort(person+1,person+m+1);
printf("Best jury has value %d for prosecution and value %d for defence:\n",p,d);
for(int i=1;i<=m;i++) printf(" %d",person[i]);
printf("\n\n");//debug 空行
}
}
};
int main()
{
mine::main();
}

4 poj1742 Coins

8.22 难度2

请先思考后再展开

楼教主的题耶
二进制拆分法解决多重背包问题

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
59
60
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=110,MAX_M=110000;
int mymax(int x,int y) {return x>y?x:y;}
int bin[20];
int a[MAX_N],b[MAX_N];
int w[MAX_N*20];
bool f[MAX_M];
void main()
{
bin[0]=1;for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
while(1)
{
int n,m;scanf("%d%d",&n,&m);
if(n==0 and m==0) break;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
int tot=0;
for(int i=1;i<=n;i++)
{
int p=0;while(bin[p+1]-1<b[i]) p++;
int r=b[i]-(bin[p]-1);p--;
for(int j=0;j<=p;j++) w[++tot]=bin[j]*a[i];
w[++tot]=r*a[i];
}
memset(f,0,sizeof f);
f[0]=1;
for(int i=1;i<=tot;i++)
for(int j=m;j>=w[i];j--)
f[j]|=f[j-w[i]];
int ans=0;
for(int i=1;i<=m;i++) ans+=f[i];
printf("%d\n",ans);
}
}
};
int main()
{
mine::main();
}

5 USACO2005 Jan Gold Naptime

8.23 难度2

请先思考后再展开

环形的dp,并且不能使用克隆法(会重复使用)
对于这种决策能自动补全的题目,可以用一种巧妙的做法————二次扫描

设 $f(i,j,0/1)$ 表示处理到第i个小时,已经休息了j个小时,当前醒/睡状态下,最大的休息值
先不考虑从昨晚就开始睡觉的情况

初始值为负无限(剔除非法状态,例如休息0正在睡)
$f(1,0,0)=f(1,1,1)=0$
$f(i,j,0)=f(i-1,j,0)$
$f(i,j,1)=max{ f(i-1,j-1,0),f(i-1,j-1,1)+w_i }$
$ans1=max{ f(n,m,0),f(n,m,1) }$
那么昨晚就开始睡觉怎么办?
$f(1,0,0)=0,f(1,1,1)=w_1$
强行重新跑一次,自动拼接
$ans2=f(n,m,1)$

$ANS=max{ ans1,ans2 }$

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=4000;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int n,m;
int w[MAX_N];
int f[2][MAX_N][2];//滚动
void dp()
{
for(int i=2;i<=n;i++)
for(int j=0;j<=mymin(i,m);j++)
{
f[i&1][j][0]=mymax(f[(i-1)&1][j][0],f[(i-1)&1][j][1]);
if(j>0) f[i&1][j][1]=mymax( f[(i-1)&1][j-1][0],f[(i-1)&1][j-1][1]+w[i] );
}
}
void main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
memset(f,-63,sizeof f);//debug 剔除非法状态
f[1][0][0]=f[1][1][1]=0;
dp();
int ans1=mymax(f[n&1][m][0],f[n&1][m][1]);
memset(f,-63,sizeof f);
f[1][0][0]=0;f[1][1][1]=w[1];
dp();
printf("%d",mymax(ans1,f[n&1][m][1]));
}
};
int main()
{
mine::main();
}

6 CF24D Broken robot

8.23 难度2

请先思考后再展开

注意题意细节,一开始看题看错了:

  1. 不能向上
  2. 可以到最后一行任意位置
  3. 停在原地的选择也算是一种行动,要计算步数
  4. 如果向左是非法选择,那么随机的时候不会考虑那边
    非常有趣的思路:用高斯消元解决局部依赖性的dp

分n个阶段去dp
同样用倒推解决期望问题
$f(i,j)=f(i,j)/4+f(i,j-1)/4+f(i,j+1)/4+f(i+1,j)/4+1$
其中 $f(i+1,j)$ 是定值
$\frac{3}{4}f(i,j)-\frac{1}{4}f(i,j-1)-\frac{1}{4}f(i,j+1)=f(i+1,j)/4+1$
每个阶段列出一个 m个m元方程组,浮点高斯消元求解即可

就这么水?呵呵
复杂度是$n^3$ ,不tle才怪
主要是高斯消元太慢了
考虑通过题目性质改良

1
2
3
4
5
6
@@
@@@
@@@
@@@
@@@
@@

形状一定是这样的
然后可以这样搞:
第一遍,顺着,第i行消第i+1的第i元,变成这样

1
2
3
4
5
6
@@
@@
@@
@@
@@
@

第二遍,倒着,第i行消第i-1行的第i个

然后就完美了
虽然大部分是自己想的,但还是有akc的一点提示,以及lxj的一点题意解释(懒得看)

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=1100;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
double f[MAX_N][MAX_N];
int m;
double a[MAX_N][MAX_N],b[MAX_N];
void guass2()//针对此题的形状
{
for(int i=1;i<=m-1;i++)
{
double t=a[i+1][i]/a[i][i];
a[i+1][i]=0;
a[i+1][i+1]-=a[i][i+1]*t;
b[i+1]-=b[i]*t;
}
for(int i=m;i>=2;i--)
{
double t=a[i-1][i]/a[i][i];
a[i-1][i]=0;
b[i-1]-=b[i]*t;
}
}
void main()
{
int n,stx,sty;scanf("%d%d%d%d",&n,&m,&stx,&sty);
if(m==1)
{
printf("%d",(n-stx)*2);
return;//f(i,j)/2=f(i+1,j)/2+1
}
for(int i=n-1;i>=stx;i--)
{
for(int j=1;j<=m;j++)
{
if(1==j or j==m)
{
a[j][j]=2;
if(j>1) a[j][j-1]=-1;
if(j<m) a[j][j+1]=-1;
b[j]=f[i+1][j]+3;
}
else
{
a[j][j]=3;
if(j>1) a[j][j-1]=-1;
if(j<m) a[j][j+1]=-1;
b[j]=f[i+1][j]+4;
}
}
guass2();
for(int j=1;j<=m;j++) if(a[j][j]!=0) f[i][j]=b[j]/a[j][j],a[j][j]=0;
}
printf("%.10lf",f[stx][sty]);
}
};
int main()
{
mine::main();
}

7 noi2001 炮兵阵地

8.26 难度2

请先思考后再展开

关键是状态怎么精妙地表示
一开始想着用6进制数,炸得很
主要是没有考虑到十字的影响很小
计算第i+1行,只要考虑第i-1和第i行,确保它们分别与运算都是0(反映列的上下影响两个)
同时可以预处理出每个行内合法的状态,也就是没有两个相邻的距离小于3(反映行)
这个状态量非常小,极限88个,可以放心搞
时间复杂度$O(n |S|^3)$

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=110;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int mysqr(int x) {return x*x;}
int bin[20];
int n,m;
int tot,S[100],siz[100];//状态,1的数量,极限88个
void pre()
{
bin[0]=1;for(int i=1;i<=m;i++) bin[i]=bin[i-1]*2;
tot=0;
for(int s=0;s<=bin[m]-1;s++)
{
int lst=-5,tmp=0;
bool bk=1;
for(int j=0;j<=m-1;j++)
if(s&bin[j])
{
tmp++;
if(j-lst<=2) bk=0;
else lst=j;
}
if(bk) S[++tot]=s,siz[tot]=tmp;
}
}
int mp[110];
bool okay(int i,int k)
{
return (mp[i]|S[k])==mp[i];
}
int f[110][100][100];
int dp()
{
memset(f,-1,sizeof f);
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++)
if((S[i]&S[j])==0 and okay(1,i) and okay(2,j))
f[2][i][j]=siz[i]+siz[j];
for(int now=2;now<=n-1;now++)//刷表法
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++) if(f[now][i][j]>=0)
for(int k=1;k<=tot;k++)
if(okay(now+1,k) and (S[i]&S[k])==0 and (S[j]&S[k])==0)
f[now+1][j][k]=mymax(f[now+1][j][k],f[now][i][j]+siz[k]);
int ans=0;
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++)
if((S[i]&S[j])==0 and okay(n-1,i) and okay(n,j))
ans=mymax(ans,f[n][i][j]);
return ans;
}
char str[20];
void main()
{
scanf("%d%d",&n,&m);
pre();
for(int i=1;i<=n;i++)
{
scanf("%s",str);
for(int j=0;j<=m-1;j++) if(str[j]=='P') mp[i]|=bin[j];
}
if(n==1)
{
int mx=0;
for(int i=1;i<=tot;i++) if(okay(1,i)) mx=mymax(mx,siz[i]);
printf("%d",mx);
}
else printf("%d",dp());
}
};
int main()
{
mine::main();
}

8 5702 Count The Repetitions

8.27 难度2

请先思考后再展开

神仙好题
看到字符串的“生成”就虚的要死
但其实字符串长度很短,可以暴力搞
具体等会讲

问题可以转化成,用 $s(s_1,n_1)$ 能生成的 $s(s_2,m’)$ 使m’最大
答案即最大的 $n_2 \times m \leq m’$

因为m’是能拆分二进制的,那么考虑能否用s1来拼出
只要有解,那么从某个位置开始的连续一段,花费一些字符长度,总是能拼出来的
那么记录具体花费(考虑到题目中的生成是不能跳跃的,那么花费代价是很明确的,也没有任何决策可言)
$f(x,p)$ 表示在s1的x开始,需要花费多少个字符,才能生成$s(s_2,2^p)$
对于p=0的起始状态,可以直接暴力尝试s2的每个字符,然后如果为了找一个字符连续找了一圈,
那么无解,这个地方的复杂度是$100^3$

倍增的转移就非常简单了(为了方便,字符串从0开始)
这时候先假设s1是无限长的,后面拆分的时候再考虑最终长度限制,因为现在还不明确
$f(x,p)=f(x,p-1)+f( x+f(x,p-1) \% |s_1|,p-1 )$

对于每次拆分,设x为当前用到什么地方,限制$x \leq n_1 \times |s_1|$
然后x从0开始,lyd不知道干嘛居然还枚举x的起点,这样显然是没意义的……
然后就没有然后了

本题ch上数据有错,多了个大括号在输入文件中,用cin可以规避
简易前往leetcode466

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
59
60
61
62
63
64
65
66
67
68
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=110;
const int INF=0x3f3f3f3f;
ll f[MAX_N][40];
int n1,n2;
char s2[MAX_N],s1[MAX_N];
void solve()
{
int len2=strlen(s2),len1=strlen(s1);
memset(f,0,sizeof f);
//暴力计算f(st,0)
for(int st=0;st<=len1-1;st++)
{
int now=st;
for(int i=0;i<=len2-1;i++)//s2
{
int tot=0;//s1
while(s1[now]!=s2[i])
{
now=(now+1)%len1;
if(++tot>=len1) {puts("0");return;}//debug
}
now=(now+1)%len1;f[st][0]+=tot+1;
}
}
//预处理转移
for(int p=1;p<=30;p++)
for(int x=0;x<=len1-1;x++)
f[x][p]=f[x][p-1]+f[(f[x][p-1]+x)%len1][p-1];
//二进制拆分
ll now=0,ans=0;
for(int p=30;p>=0;p--)
if(now+f[now%len1][p]<=n1*len1)
now+=f[now%len1][p],ans+=1<<p;
printf("%lld\n",ans/n2);
}
void main()
{
while(scanf("%s%d%s%d",s2,&n2,s1,&n1)!=EOF) solve();
}
};
int main()
{
mine::main();
}

9 poj3017 Cut the Sequence

8.27 难度2

请先思考后再展开

$f(i)=min{ f(j)+mx(j+1,i) },sum(j+1,i) \leq M,0 \leq j<i$
这个柿子的可以用队列维护,但难以维护单调性

但是有一个结论:
对于一个 $j$ ,若 $j$ 可能是最优决策,则不仅要满足$sum(j+1,i) \leq M$
还要满足下列其中一个条件:

  1. $a_j=max(j,i)$ (单调递减性)
  2. $sum(j,i)>M$ (也就是说 $j+1$ 是满足条件中最小的 )
    证明:
    首先如果意会一下,就是在满足条件下,以max结果分割,每段最左边的那个
    原因是,如果存在一个满足条件的 $j-1$ ,并且和 $j$ 在同一段中,
    那么再考虑f的单调性(显然多一个数字不会更小),显然 $j-1$ 不会比 $j$ 差

上面两种情况可以分开考虑和继承
对于情况2,可以尺取法线性维护(每个 $i$ 只有一个)
对于情况1,维护一个 $a$ 单调递减的队列
不难发现,对于单调队列中的每个元素,其 $mx(j+1,i)$ 就是下一个元素的a
然后,由于条件1,在每次插入 $a_i$ 并维护单调性后,每个决策的大小是不会变的(除了单调队列最后一个元素,因为此时它还没有下一个元素)
等维护完以后,再把倒数第二个决策插入到二叉堆里面,取最大更新即可

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=110000;
const int INF=0x3f3f3f3f;
int bin[20];
ll mymin(ll x,ll y) {return x<y?x:y;}
int n;
int a[MAX_N];
int p[MAX_N];//单调队列对应位置
multiset<ll> q;
ll f[MAX_N];
void main()
{
ll m;scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>m) {puts("-1");return;}
}
int l=1,r=1;
p[1]=1;f[1]=a[1];
ll sum=a[1];int low=1;
for(int i=2;i<=n;i++)
{
//update
sum+=a[i];
while(sum>m) sum-=a[low++];
while(l<=r and p[l]<low)
{
if(l<r) q.erase(q.find( f[p[l]]+a[p[l+1]] ));
l++;
}
//push
while(l<=r and a[p[r]]<=a[i])
{
if(l<r) q.erase(q.find( f[p[r-1]]+a[p[r]] ));
r--;
}
p[++r]=i;if(l<r) q.insert(f[p[r-1]]+a[p[r]]);
//dp
f[i]=f[low-1]+a[p[l]];
if(l<r) f[i]=mymin(f[i],*q.begin());
}
printf("%lld",f[n]);
}
};
int main()
{
mine::main();
}

10 5A01 任务安排1

8.27 难度2

请先思考后再展开

最初的想法,基本上是$O(750000^2 n)$
$f(i,ed)=min{ f(j,\leq ed-s-sumT[i]+sumT[j])+ed \times (sumC[i]-sumC[j]) }$
其实可以把第二维转化为分段数量,简化状态,时间$O(n^3)$
$f(i,t)=min{ f(j,t-1)+(S \times t+sumT[i]) \times (sumC[i]-sumC[j]) }$

然后有一个神奇的经典思想,叫做“费用提前计算”,就是把当前决策产生的后效性现在就计算,这样子,如果某次决策比不过别人,没有后效性之后是不用任何担心的,再也不会更优
$f(i)=min{ f(j)+sumT[i] \times (sumC[i]-sumC[j])+S \times (sumC[n]-sumC[j]) }$
时间$O(n^2)$

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=5100;
const int INF=0x3f3f3f3f;
ll mymin(ll x,ll y) {return x<y?x:y;}
ll sumT[MAX_N],sumC[MAX_N];
ll f[MAX_N];
void main()
{
int n,S;scanf("%d%d",&n,&S);
for(int i=1;i<=n;i++)
{
int a,b;scanf("%d%d",&a,&b);
sumT[i]=sumT[i-1]+a;sumC[i]=sumC[i-1]+b;
}
memset(f,63,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
f[i]=mymin(f[i],
f[j]+sumT[i]*(sumC[i]-sumC[j])+(sumC[n]-sumC[j])*S
);
printf("%lld",f[n]);
}
};
int main()
{
mine::main();
}

11 ioi2002 Batch Scheduling

8.27 难度2

请先思考后再展开

$f(i)=min{ f(j)+sumT[i] \times (sumC[i]-sumC[j])+S \times (sumC[n]-sumC[j]) }$
把min去除,把关于j的值看做变量
$【f(j)】=【sumT[i]+S】\times sumC[j]+【f(i)-sumT[i] \times sumC[i]-S \times sumC[n]】$
看起来像一个一次函数$y=kx+b$

未完待续……

1
2

CF559C Gerald and Giant Chess

8.28 难度2

请先思考后再展开

看到黑色棋子这么少,一定是用总方案数-非法情况得到答案
然后就想着,如果统计每个黑色格子经过的数量,用容斥原理统计的话,怎么计算出多个黑色的情况?
显然是无法暴力枚举的,然后就懵逼了

其实,这是因为状态的设计有问题,导致同一条路径被多次计算
重新设计状态,设$f(x)$表示以黑格子x作为某条【经过黑格子的路径】的第一个黑格子,这样,每条路径只会被它第一个黑格子统计,这样就能不重不漏了
至于任意走的时候的方案数,可以参考前面讲到的多重集全排列
$$
f(i)=C_{x_i+y_i-2}^{x_i-1} -
\sum_{{ j|x_j \leq x_i 且 y_j \leq y_i }}
f(j) \times C_{x_i-x_j+y_i-y_j}^{x_i-x_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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=2100;
const ll MOD=1e9+7;
ll qpower(ll a,ll e)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=ans*a%MOD;
a=a*a%MOD;e>>=1;
}
return ans;
}
ll fac[210000],invfac[210000];//debug 开太小了,因为x+y
ll C(int n,int m)
{
return fac[n]*invfac[m]%MOD*invfac[n-m]%MOD;
}
struct Nod
{
int x,y;
}p[MAX_N];
bool cmp(Nod a,Nod b)
{
return a.x<b.x or (a.x==b.x and a.y<b.y);
}
ll f[MAX_N];
void main()
{
fac[0]=1;invfac[0]=1;
for(int i=1;i<=200000;i++) fac[i]=fac[i-1]*i%MOD,invfac[i]=qpower(fac[i],MOD-2);
int h,w,n;scanf("%d%d%d",&h,&w,&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+n+1,cmp);
p[n+1].x=h;p[n+1].y=w;//等价
for(int i=1;i<=n+1;i++)
{
f[i]=C(p[i].x+p[i].y-2,p[i].x-1);
for(int j=1;j<=i-1;j++)
if(p[j].x<=p[i].x and p[j].y<=p[i].y)
{
f[i]-=f[j]*C(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%MOD;
f[i]=(f[i]%MOD+MOD)%MOD;
}
}
printf("%I64d",(f[n+1]%MOD+MOD)%MOD);
}
};
int main()
{
mine::main();
}

poj1737 Connected Graph

8.28 难度2

请先思考后再展开

通常而言,计数类dp需要划分结构来继承,但现在处理的“连通无向图”很难划分
所以现在考虑能否算出【任意无向图数量-不连通的无向图数量】
任意无向图数量显然为$2^{n(n-1)/2}$
对于不连通的无向图数量,可以划分出多个联通块
又是运用某个不知名的经典思想,只分割出单一的一个来避免重复计数,剩下的内部还是任意(不能和分割出来的连通)

设 $f(i)$ 表示一个大小为n的连通无向图数量
$f(i)=2^{i(i-1)/2}-\sum_{j=1}^{i-1} f(j) \times C_{i-1}^{j-1} \times 2^{(i-j)(i-j-1)/2}$
代码略

CEOI2002 A decorative fence

8.28 难度3

请先思考后再展开

整体思路:因为要找第k大,依次枚举每个位置,枚举在这上面放什么,
然后计算如果这样放,后面的方案数T
如果$k \leq T$,那么证明这是正确的,继续往下找,否则$k-=T$
这个思想在【树状数组、各种平衡树中找第k大】等应用中都有体现,不过本题没法也没必要分治

具体而言,设当前位置为i,并假设现在放了一块长度为h的木板作为0低位1高位
高低位在第一个确定以后,就是轮流的了,所以说第一个要特判
那么怎么计算方案数呢?
设 $f(i,j,0/1)$ 表示用i个木板,其中最左边那个在其中是第i小且作为0低位1高位,的方案数
那么此时就是$f[n-i+1][h在剩下中的排名][递推出的当前高低位]$

注意到我们用排名而不是具体的值来表示
这样子就不用考虑左边用剩下什么,而只要考虑高低位所需要的相对大小关系就好了(类似离散化)
而且因为和具体的值没有关系,放在外面预处理也是可以的

这个dp方程也不是太好想
可以从放入后的结果考虑,然后思考什么状态能转移过来:
在插入后,最左边那个的排名是j
如果是低位,那么插入后的排名,可以在它右边的就是 j+1~i ,还原到i-1时就是 j~i-1
$f(i,j,0)=\sum_{p=j}^{i-1} f(i-1,p,1)$
如果是低位,那么插入后的排名,可以在它右边的就是 1~j-1 ,还原到i-1时依旧是 1~j-1
$f(i,j,1)=\sum_{p=1}^{j-1} f(i-1,p,0)$

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=30;
const int INF=0x3f3f3f3f;
ll f[MAX_N][MAX_N][2];
void preDP()
{
f[1][1][0]=f[1][1][1]=1;
for(int i=2;i<=20;i++)
{
for(int j=1;j<=i;j++)
{
for(int p=j;p<=i-1;p++) f[i][j][0]+=f[i-1][p][1];
for(int p=1;p<=j-1;p++) f[i][j][1]+=f[i-1][p][0];
}
}
}
void main()
{
preDP();
int T;scanf("%d",&T);
while(T--)
{
int n;ll k;scanf("%d%lld",&n,&k);
int last,now;
for(last=1;last<=n;last++)//第一个(要从小到大)
{
now=1;
if(k>f[n][last][1])//由于第一位已经确定,字典序由第二位决定,先下降
{
k-=f[n][last][1],now=0;
if(k>f[n][last][0]) {k-=f[n][last][0];continue;}
}
break;
}
printf("%d",last);
bool v[30];memset(v,0,sizeof v);v[last]=1;
for(int i=2;i<=n;i++)//填第i位,n^3
{
now^=1;
for(int len=1;len<=n;len++)//要从小到大
{
if(v[len]) continue;
if(now and last>len) continue;
if(!now and last<len) continue;
int tot=0;for(int j=1;j<=len-1;j++) if(!v[j]) tot++;
if(k<=f[n-i+1][tot+1][now]) {v[len]=1;last=len;printf(" %d",len);break;}
else k-=f[n-i+1][tot+1][now];
}
}
puts("");
}
return;
}
};
int main()
{
mine::main();
}

poj3208 Apocalypse Someday

8.28 难度2

请先思考后再展开

运用和上一道题类似的思想
考虑每一个位置,枚举其数字,将后面能够让当前数字变成魔鬼数有多少种方案

而要称为魔鬼数,需要考虑三点:

  1. 前面部分最后连续的6的数量(也可能已经是魔鬼数,此时后面可以任意填)
  2. 这一位是否是6(衔接、延长)
  3. 后面的方案

这里后面的方案同样是预处理,但又要考虑到其前面6的个数
以下内容包含前导0
设 $f(i)$ 表示i位魔鬼数的数量
$g(i,0/1/2)$ 表示最后有连续 $0/1/2$ 个6,但不是魔鬼数的数量(避免重复)

显然有如下柿子
$f(i)=g(i-1,2)+10\times f(i-1)$
$g(i,0)=g(i-1,0)+g(i-1,1)+g(i-1,2)$
$g(i,1)=g(i-1,0)$
$g(i,2)=g(i-1,1)$

但要注意边界$g(0,0)=1$
本来直接写出了i=1的情况错了,好想是因为后面要用到,而不仅预处理

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=30;
const int INF=0x3f3f3f3f;
int mymin(int x,int y) {return x<y?x:y;}
int f[20],g[20][3];
void preDP()
{
g[0][0]=1;//debug 不止预处理,拆分的时候也要用到
for(int i=1;i<=10;i++)
{
g[i][0]=9*(g[i-1][0]+g[i-1][1]+g[i-1][2]);
g[i][1]=g[i-1][0];
g[i][2]=g[i-1][1];
f[i]=g[i-1][2]+10*f[i-1];
}
}
void main()
{
preDP();
int T;scanf("%d",&T);
while(T--)
{
int k;scanf("%d",&k);
int ln=3;while(k>f[ln]) ln++;//确保第一个不会选出0
int lst=0;//3表示已经是
for(int now=ln;now>=1;now--)
{
for(int i=0;i<=9;i++)
{
int num=f[now-1];//有多少种填法能让整个数是魔鬼数
if(lst==3) num+=g[now-1][0]+g[now-1][1]+g[now-1][2];
else if(i==6)
{
if(lst>=0) num+=g[now-1][2];
if(lst>=1) num+=g[now-1][1];
if(lst>=2) num+=g[now-1][0];
}
if(k>num) {k-=num;continue;}
if(lst<3)
{
if(i==6) lst++;
else lst=0;
}
printf("%d",i);
break;
}
}
puts("");
}
return;
}
};
int main()
{
mine::main();
}

Ahoi2009 同类分布

8.28 难度2

请先思考后再展开

本来觉得是一道神题
学完数位dp后,就觉得是一道水题了(主要是太套路,太常规)

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
59
60
61
62
63
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=30;
const int INF=0x3f3f3f3f;
ll f[20][170][170];
bool v[20][170][170];
int ed;
int num[20];
ll dec[20];//%ed下
ll calc(int ln,int sum,int r,bool mask)//长度,剩下和,余数,顶位
{
if(sum<0) return 0;
if(ln<=0) return sum==0 and r==0;
if(!mask and v[ln][sum][r]) return f[ln][sum][r];
ll tot=0;
int mx=mask?num[ln]:9;
for(int now=0;now<=mx;now++)
tot+=calc(ln-1,sum-now,(( r-now*dec[ln-1] )%ed+ed)%ed,mask and now==mx);
if(!mask) v[ln][sum][r]=1,f[ln][sum][r]=tot;
return tot;
}
ll solve(ll x)
{
int n=0;while(x>0) num[++n]=x%10,x/=10;
ll ans=0;
for(ed=1;ed<=9*n;ed++)
{
dec[0]=1;for(int i=1;i<20;i++) dec[i]=dec[i-1]*10%ed;
memset(v,0,sizeof v);
ans+=calc(n,ed,0,1);
}
return ans;
}
void main()
{
ll a,b;scanf("%lld%lld",&a,&b);
printf("%lld",solve(b)-solve(a-1));
}
};
int main()
{
mine::main();
}

###
8.28 难度2

请先思考后再展开
1
2

###
8.28 难度2

请先思考后再展开
1
2

0x5E 动态规划练习

部分题目

USACO2002 Feb BUY LOW, BUY LOWER

8.24 难度2

请先思考后再展开

难点在于统计和去重
很不好想的做法:
先处理出f,接着重新枚举一次,根据刚才的转移路径来统计答案
为了避免重复,碰到相同的数就break,因为前面的部分是无法直接更新自己的

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=5100;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int a[MAX_N];
int f[MAX_N],c[MAX_N];
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[0]=0x3f3f3f3f;
for(int i=1;i<=n;i++)
for(int j=0;j<=i-1;j++)
if(a[j]>a[i]) f[i]=mymax(f[i],f[j]+1);
c[0]=1;
for(int i=1;i<=n;i++)
for(int j=i-1;j>=0;j--)
{
if(a[j]==a[i]) break;//前面部分交给j
if(a[j]>a[i] and f[j]+1==f[i]) c[i]+=c[j];//转移
}
int ans=0;for(int i=1;i<=n;i++) ans=mymax(ans,f[i]);
int count=0;for(int i=1;i<=n;i++) if(f[i]==ans) count+=c[i];
printf("%d %d",ans,count);
}
};
int main()
{
mine::main();
}

poj1722 SUBTRACT

8.24 难度3

请先思考后再展开

非常好的一道题,思考难度略大 (就是说我太菜不会做)

转化题目:
把两个数做差后合并,就是打负号后再打括号
那么相当于把整个数列,在空位写符号,问能否得到目标数T

题目特性:
由于值域很小(-10000~10000),考虑一个可加可减的背包
$f(i,ed)$ 表示考虑到第i位,能否得到d,
-1表示不行,0表示在$i-1和i$ 之间用+,1表示-
因为有spj,能找到解就好
还原路径也非常简单

求解:
合并的做法也很巧妙
每次把连续的一段+,打上括号,也就变成了-
然后随便地把第一位连续输出长度个即可
这样把所有+处理完,只剩-,那么同样直接把第一个位置连续地输出就好了

对了,注意第一个符号不能是+,否则没法变成-

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
59
60
61
62
63
64
65
66
67
68
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=110;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int a[MAX_N];
#define f(i,j) F[i][10000+j]
int F[MAX_N][21000];
int sign[MAX_N];//0=+,1=-
void main()
{
int n,ed;scanf("%d%d",&n,&ed);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(F,-1,sizeof F);
f(1,a[1])=2;//任意的可行
for(int i=1;i<=n-1;i++)//刷表法更方便
for(int d=-10000;d<=10000;d++) if(f(i,d)>=0)
{
if(i>1) f(i+1,d+a[i+1])=0;//debug 第一个不能是+
f(i+1,d-a[i+1])=1;
}
for(int i=n;i>=2;i--)
{
sign[i-1]=f(i,ed);
if(sign[i-1]) ed+=a[i];
else ed-=a[i];
}
int nown=n-1,ln=0;
for(int i=n-1;i>=1;i--)
{
if(!sign[i]) ln++;//+
else
{
nown-=ln;
while(ln--) printf("%d\n",i+1);
ln=0;
}
}
nown-=ln;
while(ln>0) printf("%d\n",ln),ln--;
while(nown>0) printf("1\n"),nown--;
}
};
int main()
{
mine::main();
}

noi2001 陨石的秘密

8.24 难度2

请先思考后再展开

非常巧妙地dp设计
之前听嘎爷讲过类似的题目,就是通过一个小小的容斥表示状态
这样具体转移的时候只要关心一个上或下限就好了
以本题为例,设$f(d,a,b,c)$ 表示$深度 \leq d$ ,
同时各个括号分别用a、b、c对时,其可行方案数
这样答案就是$f(D,A,B,C)-f(D-1,A,B,C)$

转移的时候,可以通过简单的乘法原理,分成两边后,
考虑右边那个的外层是什么,然后累加起来
这样子就能够保证右边那个一定是一个块,而不是多个块,避免了重复
这一点之前也见过,把一个多子树的问题,每次只抽出一个子树,其他递归下去考虑,一样的道理
$$
f(d,a,b,c)= \\
f(d,a,b,c-k-1) \times f(d-1,0,0,k) + \\
f(d,a,b-j-1,c-k) \times f(d-1,0,j,k) + \\
f(d,a-i-1,b-j,c-k) \times f(d-1,i,j,k)
$$
时间复杂度$O(A^6 \times D)$

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
59
60
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=110;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
const int MOD=11380;
int f[40][20][20][20];
void dp(int d,int a,int b,int c)//美观
{
if(a==0 and b==0 and c==0) {f[d][a][b][c]=1;return;}
int tmp=0;
for(int k=0;k<=c-1;k++)//()
tmp=(tmp+f[d][a][b][c-k-1]*f[d-1][0][0][k])%MOD;
for(int j=0;j<=b-1;j++)//[]
for(int k=0;k<=c;k++)//()
tmp=(tmp+f[d][a][b-j-1][c-k]*f[d-1][0][j][k])%MOD;
for(int i=0;i<=a-1;i++)//{}
for(int j=0;j<=b;j++)//[]
for(int k=0;k<=c;k++)//()
tmp=(tmp+f[d][a-i-1][b-j][c-k]*f[d-1][i][j][k])%MOD;
f[d][a][b][c]=tmp;
}
void main()
{
int A,B,C,D;scanf("%d%d%d%d",&A,&B,&C,&D);
f[0][0][0][0]=1;
for(int d=1;d<=D;d++)
for(int a=0;a<=A;a++)
for(int b=0;b<=B;b++)
for(int c=0;c<=C;c++)
dp(d,a,b,c);
//debug 又被三目运算符坑了
int ans=f[D][A][B][C]-(D>0?f[D-1][A][B][C]:0);
printf("%d",(ans%MOD+MOD)%MOD);
}
};
int main()
{
mine::main();
}

noi1999 棋盘分割

8.25 难度2

请先思考后再展开

一开始看错题目了,好像是因为以前见过那样的题目:
每次切都是产生切剩下的部分的代销(像合并果子?)
那样的话,平均值不固定会非常难处理,于是就跑去膜题解了
才发现自己沙茶了(这也可能是没有样例解释的锅)
其实是指切n-1刀,最后是n个块,那么其实拼起来就是原本的块,所以平均值是固定的

稍微化简一下柿子(挺意外还有化简这回事……以后题目中见到柿子都要试一试)
$ans^2$
$=\frac{1}{n}( \sum (xi-\overline x)^2 )$
$=\frac{1}{n}( \sum (xi^2-2 x_i \overline x+\overline x^2) )$
$=\frac{1}{n}( \sum xi^2 - 2sum\overline x + \sum \overline x^2)$
$=\sum xi^2/n - \overline x^2$

代码实现就非常简单了,先二维前缀和预处理,
设$f(n,a,b,c,d)$ 表示当前还有多少次,以及当前区间
记忆化搜索,转移的时候枚举端点比较即可

poj1390 Blocks

8.26 难度2

请先思考后再展开

显然先缩点

一开始想了一个贪心的做法,每次选择一个地方消除,分治,并顺便暴力地合并左右两边来更新答案
然后发现连样例都过不去,以后应该先对着样例模拟一次的……
所以现在的主要问题还是新块合并的处理

一个非常难想的延后处理法:
设$f(l,r,k)$ 表示处理l到r的区间,同时存在一个本来不连续的长度为k的块和r相连且颜色相同

  1. 直接合并,$f(l,r,k)=f(l,r-1,0)+(k+len_r)^2$
  2. 把k交给前面的某个t($col_t=col_r$)处理,$f(l,r,k)=f(l,t,k+len_r)+f(t+1,r-1,0)$

很巧妙地通过增加维,解决了新区间合并的问题
其中也含有部分贪心的思想(例如直接把r也交给t处理)

时间复杂度方面不好估计,可能比赛的话,会感觉自己打了一个部分分?然后出来就ac了
主要是因为颜色方面的限制,不会跑满(颜色块的不相同和转移时颜色的相同互斥)
极限数据如121212121,可以自己造来跑一跑

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
59
60
61
62
63
64
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=210;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int mysqr(int x) {return x*x;}
int a[MAX_N];
int col[MAX_N],len[MAX_N];
int f[MAX_N][MAX_N][MAX_N];bool v[MAX_N][MAX_N][MAX_N];
int dp(int l,int r,int k)
{
if(l>r) return 0;
if(l==r) return mysqr(len[r]+k);
if(v[l][r][k]) return f[l][r][k];
v[l][r][k]=1;
int ans=0;
ans=mymax(ans,dp(l,r-1,0)+mysqr(k+len[r]));
for(int t=l;t<=r-1;t++)
if(col[t]==col[r])
ans=mymax(ans,dp(l,t,k+len[r])+dp(t+1,r-1,0));
return f[l][r][k]=ans;
}
void main()
{
int T;scanf("%d",&T);
int ct=0;
while(T--)
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int cnt=1;col[1]=a[1];len[1]=1;
for(int i=2;i<=n;i++)
if(a[i-1]!=a[i]) col[++cnt]=a[i],len[cnt]=1;
else len[cnt]++;
memset(v,0,sizeof v);
printf("Case %d: %d\n",++ct,dp(1,cnt,0));
}
}
};
int main()
{
mine::main();
}

hdu2196 Computer

8.26 难度2

请先思考后再展开

二次剩余,时间复杂度n
为了求出,一个数列中除了某个数以外,其他数的最大值,维护一下次大值即可
大概算是小技巧

总之第一次求出子树内距离,第二次从父亲处继承信息

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=11000;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int mysqr(int x) {return x*x;}
struct Nod
{
int hou;
int mx;
}p[MAX_N];
struct Edge
{
int y,c,g;
}e[MAX_N*2];
int ln;
void ins(int x,int y,int c)
{
e[++ln]=(Edge){y,c,p[x].hou};
p[x].hou=ln;
}
void dfs1(int x,int fa)
{
p[x].mx=0;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dfs1(y,x);
p[x].mx=mymax(p[x].mx,p[y].mx+e[k].c);
}
}
void dfs2(int x,int fa,int mx)
{
int mx1=0,mx2=0;//最大和次大值
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
if(p[y].mx+e[k].c>mx1) mx2=mx1,mx1=p[y].mx+e[k].c;
else if(p[y].mx+e[k].c>mx2) mx2=p[y].mx+e[k].c;
//忘记判断,与mx2的关系
}
p[x].mx=mymax(p[x].mx,mx);
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
int t=mx1;if(p[y].mx+e[k].c==t) t=mx2;
dfs2(y,x,mymax(t,mx)+e[k].c);
}
}
void main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
ln=0;for(int i=1;i<=n;i++) p[i].hou=0;
for(int i=2;i<=n;i++)
{
int fa,c;scanf("%d%d",&fa,&c);
ins(fa,i,c);ins(i,fa,c);
}
dfs1(1,0);
dfs2(1,0,0);
for(int i=1;i<=n;i++) printf("%d\n",p[i].mx);
}
}
};
int main()
{
mine::main();
}

直径结论,时间复杂度nlogn
这东西的证明等,自行搜索本博客“直径”

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=11000;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int mysqr(int x) {return x*x;}
struct Nod
{
int hou;
int dis,dep;
}p[MAX_N];
struct Edge
{
int y,c,g;
}e[MAX_N*2];
int ln;
void ins(int x,int y,int c)
{
e[++ln]=(Edge){y,c,p[x].hou};
p[x].hou=ln;
}
void dfs(int x,int fa)
{
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
p[y].dis=p[x].dis+e[k].c;
dfs(y,x);
}
}
int bin[20];
int f[MAX_N][20];
void pre(int x,int fa)
{
f[x][0]=fa;for(int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
p[y].dis=p[x].dis+e[k].c;
p[y].dep=p[x].dep+1;
pre(y,x);
}
}
int LCA(int x,int y)
{
if(p[x].dep<p[y].dep) swap(x,y);
for(int i=19;i>=0;i--)
if(p[x].dep-p[y].dep>=bin[i])
x=f[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--) if(p[x].dep>=bin[i] and f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int getdis(int x,int y)
{
return p[x].dis+p[y].dis-2*p[LCA(x,y)].dis;
}
void main()
{
bin[0]=1;for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
int n;
while(scanf("%d",&n)!=EOF)
{
memset(f,0,sizeof f);
ln=0;for(int i=1;i<=n;i++) p[i].hou=0;
for(int i=2;i<=n;i++)
{
int fa,c;scanf("%d%d",&fa,&c);
ins(fa,i,c);ins(i,fa,c);
}
int a=1;p[1].dis=0;dfs(1,0);
for(int i=1;i<=n;i++) if(p[i].dis>p[a].dis) a=i;
int b=a;p[a].dis=0;dfs(a,0);
for(int i=1;i<=n;i++) if(p[i].dis>p[b].dis) b=i;
p[1].dis=0;p[1].dep=1;pre(1,0);
for(int i=1;i<=n;i++) printf("%d\n", mymax(getdis(i,a),getdis(i,b)) );
}
}
};
int main()
{
mine::main();
}

HNOI2011 XOR和路径

8.26 难度2

请先思考后再展开

xor是对整数的运算,所以无法求出期望递推式
如果把每个位置拆分(还是那个套路,二进制运算,不同数位间互不影响)
那么只要考虑每个数位位置是1的概率,就能求出期望(权值确定,为1)

依旧是倒推,设$f(x)$ 表示当前x到n,异或和这一位是1的概率
当$w_i=0$,$f(x)+=f(y)/tot$
当$w_i=1$,$f(x)+=(1-f(y))/tot=1/tot-f(y)/tot$
然后高斯消元即可

这道题卡精度,eps简易设置为1e-8

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=110;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int mysqr(int x) {return x*x;}
const double eps=1e-8;
bool iszero(double x) {return x>=-eps and x<=eps;}
int tot[MAX_N];
int hou[MAX_N];
struct Edge
{
int y,c,g;
}e[21000];
int ln=0;
void ins(int x,int y,int c)
{
e[++ln]=(Edge){y,c,hou[x]};
hou[x]=ln;
tot[x]++;
}
int bin[40];
double a[MAX_N][MAX_N],b[MAX_N];
void gauss(int n,int m)
{
for(int i=1;i<=m;i++)
{
int nx=0;for(int j=i;j<=n;j++) if(!iszero(a[j][i])) {nx=j;break;}
swap(b[nx],b[i]);for(int k=1;k<=m;k++) swap(a[nx][k],a[i][k]);
for(int j=1;j<=n;j++)
{
if(i==j or iszero(a[j][i])) continue;
double t=a[j][i]/a[i][i];
b[j]-=b[i]*t;for(int k=1;k<=m;k++) a[j][k]-=a[i][k]*t;
}
}
}
void main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
int n,m;scanf("%d%d",&n,&m);
while(m--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);if(x!=y) ins(y,x,c);//debug 自环不能建双向边
}
double ans=0;
for(int now=0;now<=30;now++)
{
memset(a,0,sizeof a);
memset(b,0,sizeof b);
//f(n)=0
for(int x=1;x<=n-1;x++)
{
a[x][x]=tot[x];
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(e[k].c&bin[now])
{
b[x]+=1;
if(y!=n) a[x][y]+=1;
}
else if(y!=n) a[x][y]-=1;
}
}
gauss(n-1,n-1);
ans+=b[1]/a[1][1]*bin[now];
}
printf("%.3Lf",ans);
}
};
int main()
{
mine::main();
}

SCOI2010 股票交易

8.29 难度2

请先思考后再展开

设 $f(i,k)$ 表示在第i天,拥有k个股票的最大现金
答案即 $max f(T,1…maxp)$
可能从 $f(j \leq i-w-1,k2 \leq maxp)$ 转移
注意到第二维、决策都和第一维没有关系
可以考虑一个经典的做法:把最优值后置,减少转移时间
也就是说,直接取值 $f(i-w-1,k2 \leq maxp)$ 或者 $f(i-1,k)$
时间复杂度为$O(n^3)$

在这种连log都不能要,必须省掉一个n的时候,不妨考虑一下单调性
①买入
$f(i,k)=max { f(i-w-1,k2 \geq k-As_i)+k2 \times Ap_i }-k \times Ap_i$
②卖出
$f(i,k)=max { f(i-w-1,k2 \geq k+Bs_i)+k2 \times Bp_i }-k \times Bp_i$

编号越大,贡献范围越大,维护一个编号递增,贡献递减的单调队列即可
无脑开2n个单调队列,继承于i-w-1,维护i,时空都是完全没毛病的
代码略

USACO2006 Nov Silver Round Numbers

8.29 难度1

请先思考后再展开

按照套路来就好了

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=40;
const int INF=0x3f3f3f3f;
int num[MAX_N];
int f[MAX_N][MAX_N][MAX_N];
bool v[MAX_N][MAX_N][MAX_N];
int calc(int ln,int now0,int now1,bool iszero,bool top)
{
if(ln==0) return now0>=now1;
if(!iszero and !top and v[ln][now0][now1]) return f[ln][now0][now1];
int mx=top?num[ln]:1;
int cnt=0;
for(int now=0;now<=mx;now++)
cnt+=calc(ln-1,now0+( iszero?0:(now==0) ),now1+(now==1),iszero and (now==0),top and (now==mx));
if(!iszero and !top) v[ln][now0][now1]=1,f[ln][now0][now1]=cnt;
return cnt;
}
int solve(int t)
{
int ln=0;while(t>0) num[++ln]=t%2,t/=2;
return calc(ln,0,0,1,1);
}
void main()
{
int l,r;scanf("%d%d",&l,&r);
printf("%d",solve(r)-solve(l-1));
}
};
int main()
{
mine::main();
}

###
8.28 难度2

请先思考后再展开
1
2

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/18f8.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%