动态规划·朴素 DP 思路引导

前言：

不知道各位有没有这样的想法，就是在碰到一道题，感觉它很像 DP，也确实是 DP，但却死活不会设计状态，设计出的状态也不会转移，出考场才发现原来状态那么简单，或者是自己之前 Pass 掉的做法。

我一直都有这样的困惑，所以写了一些记录，有时候状态的设计是靠经验和直觉，也有时候是根据推理得出的。

这部分记录是朴素 DP，不经过优化的思路引导，并不权威，只是分享自己的记录，也希望对各位有帮助。如果有漏的，出错的地方，希望各位 直接指出，谢谢 QAQ。

优化 DP 基本是建立在朴素 DP 设计好，然后根据一些套路 / 状态转移过程种需要优化的地方使用一些 数据结构 如线段树，单调队列等进行优化，又或者是根据一些性质进行决策优化等等，在这里不展开，如果有机会我会再开一篇专栏写。

我会放一些关于 DP 的一些基础，然后放几道我感觉有引导性的题目，和题解不同的是，我会注重思考的过程，而非算法本身。

推荐题单：

动态规划

这部分主要是给出一些动态规划的基础，让思考有个底，不然没有目的的思考相当于边发呆边等灵感。

不带什么引入了，~~觉得生硬受着~~。

DP 既指拆分为子问题，通过子问题最优策略转移为整体问题最优策略得出结果的算法过程，也指分阶段思考，阶段性转移的思想。

需要满足的条件是：

无后效性。设立的状态的决策不会受到之前决策的选择影响。
最优化原理。可以拆分为若干个子问题，每个子问题的最优即为整体问题的最优。

那么当我们设计一个状态时，就需要思考这两个条件，如果成立，那么再思考状态的缩减 / 具体的转移。否则先思考能否通过添加一些状态的描述使条件满足，或者转移的时候将后续可计算的影响直接统计，不然就直接推翻，不要去想着在状态转移里分类讨论，如果是分类讨论可以解决的事情，那么添加状态描述一定可以，否则就是一个深坑，只会白白浪费时间。

状态的设计前人也总结了算法框架，并做了分类，所以我们思考就可以根据分类应用的限制缩小思考范围，减小时间成本。

背包问题

一类 DP 问题，通常有价值和体积的限制，或者需要将问题转换为背包适用的模型，数据范围视情况而定。

分类有：01 背包，完全背包，分组背包，多重背包等，也可以应用到树上，成为树上背包。

区间 DP

可以通过子区间转换为整体，通常以区间左右端点位置为状态，以区间长度为阶段性转移，常见适用数据范围为

N \le 10^4

。

常见题型是合并操作，或者是，移动拾取一些奇怪的东西等，当然还有别的，别被局限住了。常见的套路是断环成链，应用于首尾相接的情况。

状压 DP

用当前状态转换为任意进制数字表示，并作为 DP 状态，通常数据范围较小，

N \le 25

。当然有时候题面会藏起来实际的状态和其范围使它不那么像状压，所以要留个心眼。

在棋盘上也有按格转移的插头 DP。

数位 DP

对于数进行转移，比较数学，同样数据范围视情况而定。

树型 DP

比较重要的 DP，在树上进行 DP，两种常用模型是树上背包，换根 DP，当状态只与深度相关时可以进行长链剖分进行优化。

当给出的是一颗基环树时，常用的操作是找到环，然后将其中一条边单独考虑，然后断掉形成一颗树，再进行 DP。

图上 DP

在图上根据拓扑序进行转移，如果是有向带环图，则需要进行缩点。

的题目

打乱顺序放几道我在这段时间里刷到的一些比较舒服的 DP 题目，或者两三年前扔在做题计划被我想起来的题目。

原题会放在最后面。

分别会有：

启示：给一些没有思路的同学一些启发。
答案：在提示折叠框中，作为启示的答案。
Solution.：作为整道题目的答案与讲解。
Code.：在讲解中，作为题目的正确答案，会提供注释。

T1

题目描述：

给出一颗以

0

为根节点的有根树，点有点权

v

与颜色，边有边权

d

，一开始除了根节点是白色，其他的节点都是黑色。
定义：一个黑色节点的代价为此节点到达祖先中最近的白色节点的距离

\times

此点权。一个白色节点的代价为

0

。
可以至多选择

k

个黑色节点进行染色使其变为白色，求最小代价和。

输入：

第

1

行包括两个整数

n

和

k

。
第

2

到

n+1

行每行分别有三个整数。第

i+1

行分别表示第

i

个点的点权，父节点和与父节点的距离。

输出：

一个整数表示最小代价。

输入输出样例 #1

输入 #1

CPP

输出 #1

CPP

数据范围

2\le n\le 100,1\le k\le \min(n,50)，0\le w_i\le 10^4,1\le d_i\le 10 ^4

。

启示：状态的设立需要推导答案的计算过程。

思考：
答案和什么相关？
对于一个点其自身有什么状态？
能否通过其设立状态？

浅层答案

可以发现，一个点的代价只与最近的祖先位置相关。
而对于一个点，自身的状态有点的编号和点的颜色。
而点的颜色数量有其限制。

那么应该如何设计状态？

答案的本源

设立状态

f_{i,j,k,0/1}

表示第

i

个节点最近的白色祖先为

j

，以

i

节点为根的子树内有

k

个白色节点，且第

i

个节点的颜色为

0/1

时，其子树的最小代价。

嗯，很完美的状态，那么，转移呢？

启示：状态的转移需要拆分贡献的相互联系。

思考：
每一个节点的状态与其子节点的状态有什么关联？
答案的计算是否与这种联系直接相关？

浅层答案

当这个节点为白色时，子节点的最近白色祖先就是这个节点。
如果这个节点不是，那么子节点与此节点的最近白色祖先相同。

那么应该如何转移？

答案的本源

推导出以上，答案就呼之欲出了，显然就是一个变形的树上背包，具体转移看代码：

CPP

void dp(long long u){
 stac[++tot]=u;//使用栈处理祖先
 for(int i=head[u];i;i=e[i].nxt){//逐个遍历
  int v=e[i].to;
  dep[v]=dep[u] + e[i].w,dp(v);
  for(int j=1;j<=tot;j++)
  for(int k=K;k>=0;k--){
   f[u][stac[j]][k][0]+=f[v][stac[j]][0][0],
   f[u][stac[j]][k][1]+=f[v][u][0][0];
   for(int l=1;l<=k;l++)
    f[u][stac[j]][k][0]=
    min(f[u][stac[j]][k][0],f[v][stac[j]][l][0]+f[u][stac[j]][k-l][0]),
    f[u][stac[j]][k][1]=
    min(f[u][stac[j]][k][1],f[v][u][l][0]+f[u][stac[j]][k-l][1]);
  //我尽量让它好看点了，但是太长，自动换行看起来很丑，我就只能加上一些手动换行了。
   }
  }
  for(int i=1;i<=tot;i++){//背包
   for(int j=K;j>=1;j--)
    f[u][stac[i]][j][0]=
min(f[u][stac[i]][j][0]+w[u]*(dep[u]-dep[stac[i]]),f[u][stac[i]][j-1][1]);
    f[u][stac[i]][0][0]+=w[u] * (dep[u]-dep[stac[i]]);
  }
  tot --;
}

那么，如何求解最终答案？

启示：状态的答案需要回溯推理的本质含义。

思考：
回归题目。
回归状态的设计和具体意思？
怎么使用状态表示最终答案？

答案的本源

显而易见，因为根节点本身为白色，且

k

个机会全部使用肯定更优，那么答案就是当根节点，无最近白色公共祖先，子树内有

k

个白色节点，且自身为白色节点时的最优解。

Solotion. 所有伟大源于细节

在做这道题前，我做了另一道很相似的树上背包，但是和这道题不同的是，当前状态与祖先并没有直接相关。因此我带入思维惯性，设计了一个缺少祖先影响的状态而耗费时间很久，最后才反应过来。

不妨总结一下这道题的思路流程：

首先，我们先判断出这道题是一道 DP 题：
暂时没有显然的贪心策略且树本身带有很强的子结构。

然后，我们设立状态：分析答案的计算过程，然后带入状态设计，最终发现是变形树上背包。

接着转移，思考自身状态与子状态之间的联系。

最后回归答案，试着用状态表示最终的答案。

结束。

Code.

CPP

#include<bits/stdc++.h>
using namespace std;
long long n,K;
struct wbx{
	int nxt,to,w;
}e[100005];
long long head[1000005],cnt;
long long w[1000005];
long long f[105][105][55][2];
long long dep[105];
long long stac[105],tot;
void add(long long x,long long y,long long w){
	e[++cnt]={head[x],y,w},head[x]=cnt;
}
void dp(long long u){
 stac[++tot]=u;
  for(int i=head[u];i;i=e[i].nxt){
   int v=e[i].to;
   dep[v]=dep[u]+e[i].w;
   dp(v);
   for(int j=1;j<=tot;j++)
    for(int k=K;k>=0;k--){
     f[u][stac[j]][k][0]+=f[v][stac[j]][0][0];
     f[u][stac[j]][k][1]+=f[v][u][0][0];
     for(int l=1;l<=k;l++){
       f[u][stac[j]][k][0]=
	     min(f[u][stac[j]][k][0],f[v][stac[j]][l][0]+f[u][stac[j]][k-l][0]);
       f[u][stac[j]][k][1]=
	     min(f[u][stac[j]][k][1],f[v][u][l][0]+f[u][stac[j]][k-l][1]);
     }
	}
  }
  for(int i=1;i<=tot;i++){
   for(int j=K;j>=1;j--)
   f[u][stac[i]][j][0]=
     min(f[u][stac[i]][j][0]+w[u]*(dep[u]-dep[stac[i]]),f[u][stac[i]][j-1][1]);
   f[u][stac[i]][0][0]+=w[u]*(dep[u]-dep[stac[i]]);
  }
  tot--;
} 
int main()
{
    cin>>n>>K;
    for(int i=1;i<=n;i++){
    	int x,y,z;
    	cin>>w[i]>>y>>z;
    	add(y,i,z);
    }
    dp(0);
    cout<<f[0][0][K][0];
	return 0;
}

T2

题目描述

给出一个

n

个点，

m

条边的无向图。可以选择一个点作为起点

r

，求选择一些边使无向图联通的最小总代价。
定义

u

到

v

的代价为

r

到

u

路径上的点数

\times

边权。

输入格式

第一行两个用空格分离的正整数

n,m

。
接下来

m

行，每行三个用空格分离的正整数，表示一条边的两个端点与边权。

输出格式

一个正整数，表示最小的总代价。

输入输出样例 #1

输入 #1

CPP

输出 #1

CPP

输入输出样例 #2

输入 #2

CPP

输出 #2

CPP

【数据规模与约定】
对于

20\%

的数据：保证输入是一棵树，

1 \le n \le 8

，

v \le 5\times 10^3

且所有的

v

都相等。
对于

40\%

的数据：

1 \le n \le 8

，

0 \le m \le 10^3

，

v \le 5\times 10^3

且所有的

v

都相等。
对于

70\%

的数据：

1 \le n \le 8

，

0 \le m \le 10^3

，

v \le 5\times 10^3

。
对于

100\%

的数据：

1 \le n \le 12

，

0 \le m \le 10^3

，

v \le 5\times 10^5

。

启示：性质有提示

保证输入是一棵树？
为什么要这样说？

浅层答案

容易发现，答案必定是一颗树，那么与代价的计算相关。

答案的本源

代价的计算为深度

\times

边权。

启示：数据有异常

n

这么小，对于做法有什么提示？
符合哪种类型的 DP？

浅层答案

状压。状态怎解？

答案的本源

设立状态：

f_{i,j}

表示每个节点是否选择的状态为

i

，且到达第

j

层的最小代价和。

那么我们可以直接枚举子集并进行转移。

Solution. 宇宙有天才

这题的思维难度不算很大，所以启示写这么少，也是为了引导一下思考的正确性。

思考下我们从这道题中得到了什么？看一下给出的特殊性质，通常都是一些提示，然后再联系题目，最终敲定答案。

时间复杂度的计算可以自己计算，简单且繁琐的东西我就不搞了。

需要注意一下重边的情况。

Code.

CPP

#include<bits/stdc++.h>
using namespace std;
long long n,m;
struct wbx{
	long long to,nxt,w;
}e[5005],Fzy[5005];
long long head[10005],cnt;
void add(long long x,long long y,long long w){
	e[++cnt]={y,head[x],w},head[x]=cnt;
}
long long f[1<<16][20];
long long ans=1e12;
void dfs(long long x,long long num){
	long long s[20],y=0;
	memset(s,0x3f3f,sizeof(s));
	set<long long>son;
	for(int i=0;i<n;i++){
		if(x&(1<<i)) for(int j=head[i];j;j=e[j].nxt)
			if(!(x&(1<<e[j].to)))
			s[e[j].to]=min(s[e[j].to],num*e[j].w),
			son.insert(e[j].to);
	}
	for(int i=1;i<(1<<son.size());i++){//枚举子集 
		int y=0,w=0,j=0;
		for(auto v:son){
			if(i&(1<<j)) y|=(1<<v),w+=s[v];
			j++;
		}
		if(f[x][num]+w<f[x|y][num+1])
			f[x|y][num+1]=f[x][num]+w,dfs(x|y,num+1);
	}
	if(x==(1<<n)-1) ans=min(ans,f[x][num]); 
}
bool cmp(wbx x,wbx y){
	if(x.nxt!=y.nxt) return x.nxt<y.nxt;
	if(x.to!=y.to) return x.to<y.to;
	return x.w<y.w;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,v;
		cin>>x>>y>>v,Fzy[i]={x-1,y-1,v};
	}
	sort(Fzy+1,Fzy+1+m,cmp);
	for(int i=1;i<=m;i++){//去重边 
		if(Fzy[i].to==Fzy[i-1].to && Fzy[i].nxt==Fzy[i-1].nxt) continue;
		add(Fzy[i].to,Fzy[i].nxt,Fzy[i].w);
		add(Fzy[i].nxt,Fzy[i].to,Fzy[i].w);
	}
	for(int i=0;i<=(1<<n);i++)
		for(int j=2;j<=n;j++)
			f[i][j]=1e12;
	for(int i=0;i<n;i++)
		dfs(1<<i,1);//枚举每一个节点作为起点 
	cout<<ans;
	return 0;
}

T3

原谅我真的不会简化题意。

题目描述

将大海近似的看做

x

轴建立一个竖直的平面直角坐标系，你所在的初始位置在

x

轴上。一开始空中有

N

个彩蛋，对于第

i

个彩蛋，他的初始位置用整数坐标

(x_{i}, y_{i})

表示，游戏开始后，它匀速沿

y

轴负方向下落，速度为

v_{i}

单位距离 / 单位时间。你的初始位置为

(x_{0}, 0)

，你可以沿

x

轴的正方向或负方向移动，你的移动速度是

1

单位距离 / 单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋的

y

坐标的千分之一。
求在收集到所有彩蛋的基础上，得到的分数最高。

输入格式

第一行为两个整数

N

，

x_{0}

用一个空格分隔，表示彩蛋个数与你的初始位置。第二行为

N

个整数

x_{i}

，每两个数用一个空格分隔，第

i

个数表示第

i

个彩蛋的初始横坐标。
第三行为

N

个整数

y_{i}

，每两个数用一个空格分隔，第

i

个数表示第

i

个彩蛋的初始纵坐标。
第四行为

N

个整数

v_{i}

，每两个数用一个空格分隔，第

i

个数表示第

i

个彩蛋匀速沿

y

轴负方向下落的的速度。

输出格式

一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。

输入输出样例 #1

输入 #1

CPP

输出 #1

CPP

0.000

说明 / 提示

对于

30\%

的数据，

N\leq 20

。

对于

60\%

的数据，

N\leq 100

。

对于

100\%

的数据，

-10^4 \leq x_{i},y_{i} \leq 10^4

，

0\leq v_{i} \leq 10^4

，

N \leq 1000

。

启示：答案藏于过往的罅隙

看到题面，有没有让你想起一些类型？
根据经验，状态应该如何设计？

浅层答案

区间 DP。

答案的本源

设计状态

f_{i,j},g_{i,j}

分别表示将

i,j

收集后位置在

i,j

。

啊？不是有后效性吗？

启示：未来的答案当前敲定

别慌，回看前面动态规划基础给出的应对策略。

浅层答案

因为当前耗费的时间对剩余彩蛋所造成的影响是可计算的。

答案的本源

减去此次移动使用时间所造成的损失。

Solution. 而现在的答案…

比较套路化的题目，在考前做几道这种题积累一下常见 trick 有奇效。

Code.

CPP

#include<bits/stdc++.h>
using namespace std;
long long n,x0;
long long sum;
long long s[1000005];
struct wbx{
	long long x,y,v;
}a[1000005];
bool cmp(wbx x,wbx y){return x.x<y.x;}
long long f[1005][1005],g[1005][1005];
long long Fzy(long long l,long long r){return s[n]-s[r]+s[l-1];}
int main(){
	memset(f,0x3f,sizeof(f));
    memset(g,0x3f,sizeof(g));
	cin>>n>>x0;
	for(int i=1;i<=n;i++) cin>>a[i].x;
	for(int i=1;i<=n;i++) cin>>a[i].y,sum+=a[i].y;
	for(int i=1;i<=n;i++) cin>>a[i].v;
	a[++n].x=x0,a[n].v=0; 
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].v;
	for(int i=1;i<=n;i++)
		if(a[i].y==0 && a[i].x==x0 && a[i].v==0)
			f[i][i]=0,g[i][i]=0;
	for(int len=2;len<=n;len++)
		for(int l=1,r=len;r<=n;l++,r++){
			f[l][r]=min(f[l][r],f[l+1][r]+Fzy(l+1,r)*(a[l+1].x-a[l].x));
			f[l][r]=min(f[l][r],g[l+1][r]+Fzy(l+1,r)*(a[r].x-a[l].x));
			g[l][r]=min(g[l][r],g[l][r-1]+Fzy(l,r-1)*(a[r].x-a[r-1].x));
			g[l][r]=min(g[l][r],f[l][r-1]+Fzy(l,r-1)*(a[r].x-a[l].x));
		}
	printf("%.3f",(sum-min(f[1][n],g[1][n]))/1000.0);
	return 0;
}

T4

拿道清新题作为结尾。

题目描述

给定一个由集合

\{-1, 0, 1\}

中的

n

个整数

x_1, x_2,\cdots, x_n

组成的序列。字节计算机是一种允许对序列进行以下操作的设备：对于任何

1 \leq i < n

，可以将

x_{i+1}

改为

x_{i+1} + x_i

。字节计算机可以存储的整数范围没有限制，即每个

x_i

可以（原则上）具有任意小或大的值。

编程实现字节计算机，使其将输入序列转换为非递减序列（即

x_1 \leq x_2 \leq \cdots \leq x_n

），并使操作次数最少。

输入格式

标准输入的第一行包含一个整数

n

(

1 \leq n \leq 1000000

)，表示（字节计算机的）输入序列中的元素个数。
第二行包含

n

个整数

x_1, x_2, \cdots, x_n

(

x_i \in \{-1, 0, 1\}

)，它们是（字节计算机的）输入序列的连续元素，元素之间用单个空格分隔。

输出格式

标准输出的第一行应输出一个整数，即字节计算机必须执行的最小操作次数，以使其输入序列成为非递减序列；如果无法获得这样的序列，则输出单词 BRAK（波兰语，意为“无”）。

输入输出样例 #1

输入 #1

CPP

6
-1 1 0 -1 0 1

输出 #1

CPP

Solution. 嗯

比较简单的题目，所以不放启示了。

首先明确，最优时转换的数只能为

-1,0,1

。

然后美美分类讨论。

先看数据范围：

n (1≤n≤1000000)

。

那么这题只能

O(n)

了。

要么贪心要么 DP。

贪心要简单一些，但是这里只写 DP。

设计 DP 的状态，先想一个问题：怎样的操作 / 状态会影响到子问题的状态？

首先，位置肯定有：设

i

表示第

i

位置的元素。

其次，元素的具体数值也很有用，而元素自身的范围也暗示了这点：

(x_i ∈\{−1,0,1\})

。

设

j\in \{-1,0,1\}

表示操作后该元素的大小 / 不操作。

状态设计到这就可以了，但是我一开始没意识到操作和不操作可以合并，后面也不想改了：

$j=1$ ：操作，操作后为 $1$ 的最少操作数。
$j=2$ ：不操作的最少操作数。
$j=3$ ：操作，操作后为 $0$ 的最少操作数。
$j=4$ ：操作，操作后为 $-1$ 的最少操作数。

思考状态如何转移。

第 $i$ $i$ 个元素本身为 $-1$ $- 1$ 。
- $j=1$ $j = 1$ ， $+2$ $+ 2$ 。
  - 前一个元素变为 $1$ 。
  - 前一个元素本身为 $1$ 且不操作。
- $j=2$ $j = 2$ ， $+0$ $+ 0$ 。
  - 前一个元素变为 $-1$ 。
  - 前一个元素本身为 $-1$ 且不操作。
- $j=3$ $j = 3$ ， $+1$ $+ 1$ 。
  - 前一个元素变为 $1$ 。
  - 前一个元素本身为 $1$ 且不操作。
- $j=4$ ， $/$ 。
第 $i$ $i$ 个元素本身为 $0$ $0$ 。
- $j=1$ $j = 1$ ， $+1$ $+ 1$ 。
  - 前一个元素变为 $1$ 。
  - 前一个元素本身为 $1$ 且不操作。
- $j=2$ $j = 2$ ， $+0$ $+ 0$ 。
  - 前一个元素变为 $-1$ 。
  - 前一个元素变为 $0$ 。
  - 前一个元素本身为 $-1$ 且不操作。
  - 前一个元素本身为 $0$ 且不操作。
- $j=3$ ， $/$ 。
- $j=4$ $j = 4$ ， $+1$ $+ 1$ 。
  - 前一个元素变为 $-1$ 。
  - 前一个元素本身为 $-1$ 且不操作。
第 $i$ $i$ 个元素本身为 $1$ $1$ 。
- $j=1$ ， $/$ 。
- $j=2$ $j = 2$ ， $+0$ $+ 0$ 。
  - 前一个元素变为 $1$ 。
  - 前一个元素本身为 $1$ 且不操作。
  - 前一个元素变为 $0$ 。
  - 前一个元素本身为 $0$ 且不操作。
  - 前一个元素变为 $-1$ 。
  - 前一个元素本身为 $-1$ 且不操作。
- $j=3$ $j = 3$ ， $+1$ $+ 1$ 。
  - 前一个元素变为 $-1$ 。
  - 前一个元素本身为 $-1$ 且不操作。
- $j=4$ $j = 4$ ， $+2$ $+ 2$ 。
  - 前一个元素变为 $-1$ 。
  - 前一个元素本身为 $-1$ 且不操作。

考虑边界状态，当

i=1

时只能不操作，且操作数为

0

。

Code.

CPP

#include<bits/stdc++.h>
using namespace std;
long long n;
long long x[1000005];
long long f[1000005][5];
//1 换 变为1
//2 不换 
//3 换，变为 0
//4 换，变为-1 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>x[i];
	f[1][1]=1e8,f[1][3]=1e8,f[1][4]=1e8;
	for(int i=2;i<=n;i++){
		if(x[i]==1){
			if(x[i-1]==-1) f[i][3]=f[i-1][2]+1,f[i][4]=f[i-1][2]+2;
			else f[i][3]=f[i][4]=1e8;
			f[i][3]=min(f[i][3],f[i-1][4]+1);
			f[i][4]=min(f[i][4],f[i-1][4]+2);
			f[i][2]=min(f[i-1][1],min(f[i-1][2],min(f[i-1][3],f[i-1][4])));
			f[i][1]=1e8;
		} 
		if(x[i]==0){
			if(x[i-1]==-1) f[i][4]=f[i-1][2]+1;
			else f[i][4]=1e8;
			f[i][4]=min(f[i][4],f[i-1][4]+1);
			f[i][3]=1e8;
			if(x[i-1]==1) f[i][1]=f[i-1][2]+1;
			else f[i][1]=1e8;
			f[i][1]=min(f[i][1],f[i-1][1]+1);
			if(x[i-1]<=0) f[i][2]=f[i-1][2];
			else f[i][2]=1e8;
			f[i][2]=min(f[i][2],min(f[i-1][3],f[i-1][4]));	
		}
		if(x[i]==-1){
			if(x[i-1]==1) f[i][1]=f[i-1][2]+2,f[i][3]=f[i-1][2]+1;
			else f[i][1]=f[i][3]=1e8;
			f[i][3]=1e8;
			f[i][1]=min(f[i][1],f[i-1][1]+2);
			if(x[i-1]==-1) f[i][2]=f[i-1][2];
			else f[i][2]=1e8;
			f[i][2]=min(f[i][2],f[i-1][4]);
			f[i][4]=1e8;
		}
	} 
	if(min(f[n][1],min(f[n][2],min(f[n][3],f[n][4])))==1e8) cout<<"BRAK";
	else cout<<min(f[n][1],min(f[n][2],min(f[n][3],f[n][4])));
	return 0;
}

原题：

T1 T2 T3 T4。

文章操作

前言：

动态规划

背包问题

区间 DP

状压 DP

数位 DP

树型 DP

图上 DP

的题目

T1

题目描述：

输入：

输出：

输入输出样例 #1

输入 #1

输出 #1

数据范围

T2

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

T3

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明 / 提示

T4

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

原题：

相关推荐

评论