模板
区间dp一般由小区间推出大的区间：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[1010][1010];
int main()
{
for(int i=0;i<n;i++)
dp[i][i]=........
for(int len=1;len<=n;len++)//区间长度
{
for(int i=0;i<n;i++)//区间起点
{
j=len-1+i;//区间终点
for(int k=i;k<j;k++)//k把[i,j]分为[i,k],[k+1,j]
{
dp[i][j]=........
}
}
}
http://acm.hdu.edu.cn/showproblem.php?pid=5115
http://blog.csdn.net/JACK_JYH/article/details/52151502
题目大意：你是一个战士现在面对，一群狼，每只狼都有一定的主动攻击力和附带攻击力。你杀死一只狼。你会受到这只狼的（主动攻击力+旁边两只狼的附带攻击力）这么多伤害~现在问你如何选择杀狼的顺序使的杀完所有狼时，自己受到的伤害最小。（提醒，狼杀死后就消失，身边原本相隔的两只狼会变成相邻，而且不需要考虑狼围城环这种情况）
输入要求：总共T组数据，每组N只狼，按顺序输入全部狼的主动攻击力和然后再按顺序输入全部狼的附带攻击力
输出要求：Case #x: y x第几组数据，y最少受到的伤害
#include<stdio.h>
#include <string.h>
#include<algorithm>
using namespace std;
#define maxn 205
int attack[maxn],assit[maxn];
int dp[maxn][maxn];
int main()
{
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",attack+i);
}
for(int i=1;i<=n;i++)
{
scanf("%d",assit+i);
}
assit[0]=0;
assit[n+1]=0;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
dp[i][j]=0x3f3f3f3f;
}//合法区间设置为无穷大，其他全部设置为0
for(int r=1;r<=n;r++)
{
for(int i=1;i<=n-r+1;i++)
{
int j=i+r-1;
for(int k=i;k<=j;k++)//设k为最后一只被杀死的狼
{
dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+attack[k]+assit[i-1]+assit[j+1]);
}
}
}
printf("Case #%d: %d\n",cas,dp[1][n]);
}
}
http://acm.hdu.edu.cn/showproblem.php?pid=5900
http://www.cnblogs.com/littlepear/p/5886036.html
题意：给n个数有key和val，相邻的并且key不互质的两个数可以消去并得到val，问最大价值和.
题解：状态转移有两个来源，第一个是假若一个区间[i，j]里面的物品被抽光之后，而且key[i-1]和key[j+1]满足题目条件的话，那么answer[i-1][i+1]=max(answer[i][j]+value[i]+value[j],answer[i][j]).假若在区间里面还剩下几个不能被抽走，区间[i,j]的最大值就相当于两个区间直接拼在一起喽answer[i][j]=max(answer[i][j],answer[i][k]+answer[k+1][j]).要判断区间[i,j]里的物品是否全都被抽光只需判定answer[i][j]==∑(k=i→ j)value[k]即可，为了这个的判断方便，这里特地的把value做成了前缀和的形式，方便判断
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 305
using namespace std;
typedef long long ll;
ll dp[maxn][maxn], key[maxn], val[maxn],sum[maxn];
ll gcd(ll a,ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
sum[0]=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%I64d",&key[i]);
for(int i=1;i<=n;i++) scanf("%I64d",&val[i]),sum[i]=val[i]+sum[i-1];
memset(dp,0,sizeof(dp));
for(int l=2;l<=n;l++)
{
for(int i=1;i+l<=n+1;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]);
if(gcd(key[i],key[j])>1)
{
if(j==i+1) dp[i][j] = val[i]+val[j];
else if(dp[i+1][j-1]==sum[j-1]-sum[i]) dp[i][j] = max(dp[i][j],dp[i+1][j-1]+val[i]+val[j]);
}
}
}
printf("%I64d\n",dp[1][n]);
}
}
http://acm.hdu.edu.cn/showproblem.php?pid=4283
有n个男屌丝事先按1,2,3,,,,,,n的顺序排好，每个人都有一个不开心值unhappy[i]，如果第i个人第k个上台找对象，那么该屌丝男的不开心值就会为（k-1)unhappy[i]，因为在他前面有k-1个人嘛，导演为了让所有男屌的总不开心值最小，搞了一个小黑屋，可以通过小黑屋来改变男屌的出场顺
。这个小黑屋是个栈，男屌的顺序是排好了的，但是可以通过入栈出栈来改变男屌的出场顺序
那么对于dp[i][j]的第i个人，就有可能第1个上场，也可以第j-i+1个上场。考虑第K个上场
即在i+1之后的K-1个人是率先上场的，那么就出现了一个子问题 dp[i+1][i+1+k-1-1]表示在第i个人之前上场的.对于第i个人，由于是第k个上场的，那么愤怒值便是val[i](k-1).其余的人是排在第k+1个之后出场的，也就是一个子问题dp[i+k][j]，对于这个区间的人，由于排在第k+1个之后，所以整体愤怒值要加上k*(sigma(i+k--j))。
#include<cstdio>
#include<string.h>
#include<cstring>
#include<algorithm>
#define maxn 105
using namespace std;
int dp[maxn][maxn],sum[maxn],arr[maxn];
int main()
{
int n,t;
scanf("%d",&t);
for(int q=1;q<=t;q++)
{
scanf("%d",&n);
sum[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",arr+i);
sum[i]=sum[i-1]+arr[i];
}
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
dp[i][j]=0x3f3f3f;
}
}
for(int r=1;r<=n;r++)
{
for(int i=1;i<=n-r+1;i++)
{
int j=i+r-1;
for(int k=1;k<=r;k++)
{
dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+arr[i]*(k-1)+dp[i+k][j]+(sum[j]-sum[i+k-1])*k);
}
}
}
printf("Case #%d: %d\n",q,dp[1][n]);
}
}
石子合并 直线型
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxn 205
using namespace std;
int dp[maxn][maxn],sum[maxn],arr[maxn];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
sum[0]=0;
for(int i=1;i<=n;i++)
{
//dp[i][i]=0;
scanf("%d",arr+i);
sum[i]=sum[i-1]+arr[i];
}
memset(dp,0x3f3f3f,sizeof(dp));
for(int i=1;i<=n;i++)
dp[i][i]=0;
for(int r=2;r<=n;r++)
{
for(int i=1;i<=n-r+1;i++)
{
int j=i+r-1;
dp[i][j]=dp[i][i]+dp[i+1][j]+sum[j]-sum[i-1];
for(int k=2;k<j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
}
printf("%d\n",dp[1][n]);
}
}
石子合并 环形
SCUT OJ 1207 http://www.scut.edu.cn/oj
#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxn 105
using namespace std;
int dp[maxn][maxn],dp2[maxn][maxn],sum[maxn][maxn],num[maxn];
int main()
{
int n;
while(scanf("%d",&n)!=EOF,n)
{
for(int i=1;i<=n;i++)
{
scanf("%d",num+i);
}
for(int i=1;i<=n;i++)
sum[i][1]=num[i];
for(int j=2;j<=n;j++)
{
for(int i=1;i<=n;i++)
sum[i][j]=sum[i%n+1][j-1]+num[i];
}
for(int i=0;i<=n;i++)
dp[i][1]=dp2[i][1]=0;
for(int r=2;r<=n;r++)
{
for(int i=1;i<=n;i++)
{
dp2[i][r]=0;
dp[i][r]=0x3f3f3f3f;
for(int k=1;k<r;k++)
{
dp[i][r]=min(dp[i][r],dp[i][k]+dp[(i+k-1)%n+1][r-k]+sum[i][r]);
dp2[i][r]=max(dp2[i][r],dp2[i][k]+dp2[(i+k-1)%n+1][r-k]+sum[i][r]);
}
}
}
int minv=0x3f3f3f3f,maxv=0;
for(int i=1;i<=n;i++)
{
maxv=maxv<dp2[i][n]?dp2[i][n]:maxv;
minv=minv>dp[i][n]?dp[i][n]:minv;
}
printf("%d %d\n",minv,maxv);
}
}
最大k乘积
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。
#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxn 15
using namespace std;
int bit[maxn];
long long dp[maxn][maxn],val[maxn][maxn];
/*
num:1345
bit[1]=1,bit[2]=3,bit[3]=4,bit[4]=5;
dp[i][j]:1-i位的最大j乘积
val[s][len] :第s位开始的长度为len的数字组成的10进制数（包含s位）
dp[i][j]=max(dp[k][j-1]*val[k][j-k]) ,1<=k<i;
*/
int main(void)
{
int n,k,num,i=0,j,m;
long long maxv;
char str[15];
while(scanf("%d%d",&n,&k)!=EOF)
{
scanf("%s",str);
for(i=0;i<n;i++)
bit[i+1]=str[i]-'0';
memset(val,0,sizeof(val));
for(i=1;i<=n;i++)
{
long long ans=0;
for(int len=1;len+i-1<=n;len++)
{
ans=ans*10+bit[i+len-1];
val[i][len]=ans;
}
}
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
dp[i][1]=val[1][i];
for(i=2;i<=n;i++)
for(j=2;j<=k;j++)
{
for(m=1;m<i;m++)
dp[i][j]=max(dp[i][j],dp[m][j-1]*val[m+1][i-m]);
}
printf("%lld\n",dp[n][k]);
}
return 0;
}
网友评论