动态规划（DP):
就是把把大问题转化为一个个小问题，然后在众多的小问题中递推得到这个大问题的最佳解（当然，这只是我个人对动态规划的理解，希望有大牛来指导改正），那么区间dp就是在区间之间进行动态规划。
那么区间dp的典型例题就是
nyoj 15 括号配对
nyoj 737 石子合并
做区间dp的题的一般步骤：
1.
首先肯定开一个dp[maxx][maxx]数组，（区间dp一般是二维）dp[i][j]就是表示i到j这个区间的最优解，那么dp[1][n]一般就是我们所要求的答案。
2.
dp数组的初始化是很重要的，根据题目要求，是全部赋值成0,还是-1，又或者是无穷大，但是更多的是（以dp[i][j]为例）i<j的时候无穷大，i>j时候为0，i=j时候是1（这个是说平常常用的初始化）。
3.
这一步就是最关键的dp转移方程，也没啥好说的，知道很难找就对了（大佬请自动忽略…）。
4.
剩下就是枚举子集和分割点，进过一系列枚举操作，就可以得到我们想要的答案了。
区间dp的一般模板：
int dp[maxx][maxx];
void init()
{
for(int i=1;i<=n;i++)
dp[i][i]=1;//根据题目要求来定
}
for(int len=1;len<=n;len++)//枚举区间长度
{
for(int i=1;i+len<=n;i++)//枚举区间起点
{
int j=len+i;//区间终点
for(int k=i;k<j;k++)//枚举区间分割点
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+v[i][j]);
}
}
nyoj 737 石子合并
题目
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
输入
有多组测试数据，输入到文件结束。
每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开
输出
输出总代价的最小值，占单独的一行
样例输入
3
1 2 3
7
13 7 8 16 21 4 18
样例输出
9
239
AC代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[450];
int dp[450][450];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
a[0]=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
a[i]+=a[i-1];
}
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
dp[i][j]=0x3f3f3f3f;
}
}
for(int l=1; l<n; l++)
{
for(int i=1; i<n; i++)
{
int j=i+l;
for(int k=i; k<j; k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[j]-a[i-1]);
}
}
}
printf("%d\n",dp[1][n]);
}
return 0;
}
nyoj 15 括号匹配（二）
题目
给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的
输入
第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100
输出
对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行
样例输入
4
[]
([])[]
((]
([)]
样例输出
0
0
3
2
AC代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[250][250];
char s[150];
int panduan(int x,int y)
{
if((s[x-1]=='['&&s[y-1]==']')||(s[x-1]=='('&&s[y-1]==')'))
{
return 1;
}
else
{
return 0;
}
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
int l=strlen(s);
memset(dp,0,sizeof(dp));
for(int i=0;i<=150;i++)
{
for(int j=i+1;j<=150;j++)
{
dp[i][j]=10000;
}
}
for(int i=0;i<=100;i++)
{
dp[i][i]=1;
}
for(int x=1;x<l;x++)
{
for(int i=l-x;i>=1;i--)
{
int j=i+x;
if(panduan(i,j))
{
dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
}
for(int k=i;k<j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
printf("%d\n",dp[1][l]);
}
return 0;
}
nyoj 460-项链
题目描述
在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为mrn（Mars单位），新产生的珠子的头标记为m，尾标记为n。
需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4⊕1)=1023=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3）=1023+1035+10510=710。
输入
有多组测试数据（<15），每组数据有两行。每组数据的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i<N时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
输出
对应每组数据，输出只有一行，是一个正整数E（E≤2.1*10^9），为一个最优聚合顺序所释放的总能量。
样例输入
4
2 3 5 10
样例输出
710
AC代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[300][2];
int dp[300][300];
int main()
{
int n,t;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i][1]);
a[i][0]=a[i-1][1];
a[i+n][1]=a[i][1];
a[i+n][0]=a[i][0];
}
a[1][0]=a[n][1];
a[1+n][0]=a[n][1];
memset(dp,0,sizeof(dp));
for(int l=1;l<2*n;l++)
{
for(int i=1;i<=n*2-l;i++)
{
int j=i+l-1;
for(int k=i;k<j;k++)
{
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+(a[i][0]*a[k][1]*a[j][1]));
}
}
}
int maxx=0;
for(int i=1;i<=n;i++)
{
maxx=max(dp[i][i+n-1],maxx);
}
printf("%d\n",maxx);
}
return 0;
}
nyoj 1023-还是回文
题目描述
判断回文串很简单，把字符串变成回文串也不难。现在我们增加点难度，给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。那么，将字符串变成回文串的最小花费是多少呢？
输入
多组数据
第一个有两个数n,m，分别表示字符的种数和字符串的长度
第二行给出一串字符，接下来n行，每行有一个字符(a~z)和两个整数，分别表示添加和删除这个字符的花费
所有数都不超过2000
输出
最小花费
样例输入
3 4
abcb
a 1000 1100
b 350 700
c 200 800
样例输出
900
for(int j=0;j<m;j++)
{
for(int i=j-1;i>=0;i–)
{
dp[i][j]=min(dp[i+1][j]+a[s[i]],dp[i][j-1]+a[s[j]]);
if(s[i]==s[j])
{
dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
}
}
}
<mark>这一段代码，每一次外循环可以保证以前j位的字符串变成回文串的代价最小，那么让j累加到m,就可以得到前m位的字符串变成回文串的代价，也就是我们所要求出的答案。</mark>
AC代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[2105][2105];
char s[2105];
int a[350];
char z[2];
int x,y;
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
scanf("%s",s);
for(int i=1; i<=n; i++)
{
scanf("%s%d%d",z,&x,&y);
a[z[0]]=min(x,y);
}
memset(dp,0,sizeof(dp));
for(int j=0;j<m;j++)
{
for(int i=j-1;i>=0;i--)
{
dp[i][j]=min(dp[i+1][j]+a[s[i]],dp[i][j-1]+a[s[j]]);
if(s[i]==s[j])
{
dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
}
}
}
printf("%d\n",dp[0][m-1]);
}
return 0;
}
京公网安备 11010502036488号