访问网站出现目录,网页制作资料,个人网页设计理念,咸阳市城乡建设规划局网站这道题考的是递推动态规划#xff0c;可能不是很难#xff0c;不过这是自己第一次靠自己想出状态转移方程#xff0c;所以纪念一下#xff1a;
要做这些题目#xff0c;首先要把题目中会出现什么状态给找出来#xff0c;然后想想他们的状态可以通过什么操作转移#xf… 这道题考的是递推动态规划可能不是很难不过这是自己第一次靠自己想出状态转移方程所以纪念一下
要做这些题目首先要把题目中会出现什么状态给找出来然后想想他们的状态可以通过什么操作转移进而写出状态转移方程
这道题的状态可以分为三个一个是已输出序列另一个是栈中序列另一个是未输入序列那有什么操作可以改变序列呢有两个操作一是未输入序列往栈中放数字操作二是栈中序列把数字输出到已输出序列。这时设置一数组f[i][j][k]i表示已输出序列长度j表示栈中序列长度k表示未输入序列的长度则可以根据红字的操作写出状态转移方程f[i][j][k]f[i][j-1][k1]f[i-1][j1][k];
其中[i][j-1][k1]变为f[i][j][k]表示操作一f[i-1][j1][k]变成f[i][j][k]表示操作二注意有些状态只能由一个操作转换而来不然就发生不可能的情况即越界比如说{2,0,1}只能由状态{1,1,1}转变而来不能由{2,-1,2}转变而来
#includebits/stdc.h
using namespace std;
int f[20][20][20];
int main(){int n;cinn;for(int i0;in;i){f[0][i][n-i]1;f[i][0][n-i]1;//这两种情况栈里数的顺序是唯一的所以个数也就为1}for(int i1;in;i){for(int j0;jn;j){for(int k0;kn;k){if(ijkn){if(jnkn-1)f[i][j][k]f[i][j-1][k1];else if(j0||kn)f[i][j][k]f[i-1][j1][k];else f[i][j][k]f[i-1][j1][k]f[i][j-1][k1];}}}} coutf[n][0][0]endl;
}
不过我又去看了别人的题解似乎更好又学到了其实我也想过用一个数的位置来看状态不过没能想得那么利索
