2019-8-5动态规划

T1：矩阵二

​ 题目：给定一个1*(2n)的矩阵（usqwedf：这不是一个2n的队列么），现让你自由地放入红色算筹和黑色算筹，使矩阵平衡[即对于所有的i(1<=i<=2n)，使第1~i格中红色算筹个数大于等于黑色算筹]

问有多少种方案满足矩阵平衡。

​ 这道题应该算是乱入的题吧，说是dp，然而他就是个递推。首先，我们可以非常快速的写一个暴力算法，然后你观察这个算法的前几位答案，你会发现，这个答案序列就是Catalan数。所以，n=100的数据规模就可以利用通项公式迅速求解出答案了。（好吧我承认其实可以用dp来解，但我就不划掉）

​ 代码：

#include
#include
#includeusing namespace std;int n; 
long long a[100000];int main(){cin >> n;a[0]=a[1]=1;a[2]=2;for (int i=3;i<=n;i++){int k=0;while (k<=i-1){a[i]+=a[k]*a[i-1-k];while (a[i]>=100) a[i]%=100;k++;}}cout << a[n] << endl;return 0;
} 

(裸题，和那一道高精度的码量没法比)

T2:数字三角形

​ 这道题可以说是所有OIer必做的题目了吧，因为要考虑长远状态下的决策，所以我们不能只选择当前状态下更大的那一个答案。而需要保存每一个步骤的最优解。所以这样的话，我们可以得到通项公式：
$$f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];$$
​ 有了通项公式，大部分的动态规划就是妥妥的水题了，我们就可以轻松地切掉了啦！

code:

#include
using namespace std;
int a[1005][1005],f[1005][1005];
int n;
int max1(int x,int y){if (x>y) return x;else return y;
}
void dac(int x){if (x==0) return;for (int i=1;i<=x;i++)f[x][i]=a[x][i]+max1(f[x+1][i],f[x+1][i+1]);dac(--x);
}
int main(){scanf("%d",&n);for (int i=1;i<=n;i++){for (int j=1;j<=i;j++)scanf("%d",&a[i][j]);}for (int i=1;i<=n;i++)f[n][i]=a[n][i];dac(n-1);cout << f[1][1] << endl;
}

(我为什么要写max函数。。。。)

T3: 最大子段和

给出一段序列，选出其中连续且非空的一段使得这段和最大。

​ 一看题意简明扼要，上手就来推状态转移方程。再定睛一看，似乎、好像、也许并不用这么麻烦……其实我们只需要线性的时间复杂度就可以轻松切掉这道题。

​ 我们可以用一个计数器p来累加当前的值。利用这个p变量不停增加数列中的数。每增加一个数就把p和ans比较一遍。显而易见的，当我们累加起来的这个和小于0的时候，我们就可以停下手中的操作，将p归零。

​ （内心OS：这真的是dp专题%%%）

#include
using namespace std;
int n;
int main(){cin >> n;int x,c=0,ans=-1000000;//这里的c即为上文中所写的p，是累加器for (int i=1;i<=n;i++){scanf("%d",&x);c+=x;if (c>ans) ans=c;if (c<0) c=0; //当小于0的时候，如果后面出现正数，那么累计起来一定比该数要小//所以在这里选择不取的决策更优}cout << ans << endl;
}

T4:编辑距离

设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：

1、删除一个字符；

2、插入一个字符；

3、将一个字符改为另一个字符；

！皆为小写字母！

（终于找到一道正儿八经的dp了！！！）

​ 首先看到这道题，就是要先确定这个问题的子问题是什么。我们会发现因为只有插入、删除、修改、不变这四种情况，所以子问题就是将字符串A变为字符串B一共需要多少步。

​ 然后我们需要确定状态。那么我在这里定义f[i,j]表示字符串A的前i位转变成字符串B的前j位最少需要几步。初始状态就是f[0][0]=0，结束状态（答案）就是f[len1][len2]里面了。

​ 确定状态转移方程。对于以上四种情况，我们可以像这样进行分类讨论：

1. 插入：$f[i,j]=f[i,j-1]+1$，就是说在原先A的前i位变为B的前(j-1)位的基础上再在末尾添加上一位。

2. 删除：$f[i,j]=f[i-1,j]+1$，即在原先A的前(i-1)位变为B的前j位的基础上删掉A的第i位；

3. 替换：$f[i,j]=f[i-1,j-1]+1$，即在原先A的前(i-1)位变为B的前(j-1)位的基础上一起在末尾添加上一位；

4. 不变：$f[i,j]=f[i-1,j-1]$，字符串的末两位相等，那就可以直接继承答案。

   有了这个状态转移方程，那么我们就可以着手写代码了。

   code

   #include
   #include
   #include
   #includeusing namespace std;string s1,s2;
   char a[2005],b[2005];
   int f[2005][2005];int work(int x,int y){if (f[x][y]!=-1) return f[x][y];if (x==0) return f[x][y]=y;if (y==0) return f[x][y]=x;int k=1;if (a[x]==b[y]) k=0;return f[x][y]=min(min(work(x-1,y)+1,work(x,y-1)+1),work(x-1,y-1)+k);
   }int main(){cin >> s1 >> s2;memset(f,-1,sizeof(f));int len1=s1.length(),len2=s2.length();for (int i=1;i<=len1;i++) a[i]=s1[i-1];for (int i=1;i<=len2;i++) b[i]=s2[i-1];work(len1,len2);cout << f[len1][len2] << endl;return 0;
   } 
   

   T5：回文字串

   回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

   比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。

   ​ 初看这一道题，一度十分迷茫，找不到解答的方向。状态定义都无从下手。为了不要步我的后尘，我们来这么思考一下：

   ​ 什么是回文串？就是从头读和从屁股读都是一个样子。那么我们就可以把原有的串来翻转一下，然后会发现这两个串一些相同的子序列长度是不需要修改的，所以我们就把问题变成了求两个字符串的最大公共子序列的问题。那么接下来的事情，就变成了照着模板打代码了。

   #include
   #include
   #include
   #includeusing namespace std;string s;
   char a[1005],b[1005];
   int f[1005][1005];int main(){cin >> s;int len=s.length();for (int i=1;i<=len;i++){a[i]=s[i-1];b[len-i+1]=a[i];}for (int i=1;i<=len;i++)for (int j=1;j<=len;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if (a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);}cout << len-f[len][len] << endl;return 0;
   } 
   

   （第一次用c++写字符串，调了半天……）

   T6: 求和

​ （由于题面过于冗长，这里就不贴上来了，这是NOIP普及组2015的T3）

​ （那么其实这道题目依然不是一道动态规划）

​ 这个题目，意思表达的已经很清楚了。朴素算法显然是 O ( n 2 ) O(n^2) O(n2)，肯定会超时。所以我们要寻求优化。这个优化，其实就是化简一个非常繁杂的多项式。

​ 那么我就不再这里写了吧……真的太长了。详情请见这位大佬的博客

​ 代码（真是自己的，毕竟P党）

varn,m,i,ans:longint;color,a:array[0..100005]of longint;sum1,sum2,sum3,sum4:array[0..1,0..100005]of longint;
begin                                  readln(n,m);for i:=1 to n doread(a[i]);for i:=1 to n doread(color[i]);for i:=1 to n doif odd(i) thenbeginans:=(ans+sum1[0][color[i]]+sum2[0][color[i]]*i+a[i]*sum3[0][color[i]]+sum4[0][color[i]]*i*a[i]) mod 10007;sum1[0][color[i]]:=(sum1[0][color[i]]+i*a[i]) mod 10007;sum2[0][color[i]]:=(sum2[0][color[i]]+a[i]) mod 10007;sum3[0][color[i]]:=(sum3[0][color[i]]+i) mod 10007;sum4[0][color[i]]:=(sum4[0][color[i]]+1) mod 10007;end elsebeginans:=(ans+sum1[1][color[i]]+sum2[1][color[i]]*i+a[i]*sum3[1][color[i]]+sum4[1][color[i]]*i*a[i]) mod 10007;sum1[1][color[i]]:=(sum1[1][color[i]]+i*a[i]) mod 10007;sum2[1][color[i]]:=(sum2[1][color[i]]+a[i]) mod 10007;sum3[1][color[i]]:=(sum3[1][color[i]]+i) mod 10007;sum4[1][color[i]]:=(sum4[1][color[i]]+1) mod 10007;end;writeln(ans);
end.

因为本人实在太弱，一个下午就只做了这么点。。。然后就贴上下午研究了半天的LIS优化好惹（逃

LIS(最长上升子序列)

​ 这个东西相信学习过dp的同学们都懂对吧。那么首先我们定义状态f[i]表示结束位为i的最长上升子序列的长度，那么我们就可以得到这样子的转移方程。：$f[i]=max(f[j]+1)(j<i且a[j]<a[i])$

​ 所以我们可以得到这样的代码：

for i:=1 to n do
begins:=0;for j:=1 to i-1 do            //枚举前缀if a[i]>a[j] then f[i]:=max(f[i],f[j]+1);    //f[i]表示以第i个数字为最后一个的最长序列if maxn

int ans=0;for (int i=1;i<=n;i++){int pos=lower_bound(g+1,g+ans+1,a[i])-g;ans=max(ans,pos);g[pos]=a[i];}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！