模板
區(qū)間dp一般由小區(qū)間推出大的區(qū)間：

#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++)//區(qū)間長度
    {
        for(int i=0;i<n;i++)//區(qū)間起點(diǎn)
        {
            j=len-1+i;//區(qū)間終點(diǎn)
            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

題目大意：你是一個戰(zhàn)士現(xiàn)在面對哈踱，一群狼互妓，每只狼都有一定的主動攻擊力和附帶攻擊力煌妈。你殺死一只狼。你會受到這只狼的（主動攻擊力+旁邊兩只狼的附帶攻擊力）這么多傷害~現(xiàn)在問你如何選擇殺狼的順序使的殺完所有狼時程癌，自己受到的傷害最小。（提醒轴猎，狼殺死后就消失嵌莉，身邊原本相隔的兩只狼會變成相鄰，而且不需要考慮狼圍城環(huán)這種情況）
輸入要求：總共T組數(shù)據(jù)捻脖，每組N只狼锐峭，按順序輸入全部狼的主動攻擊力和然后再按順序輸入全部狼的附帶攻擊力
輸出要求：Case #x: y x第幾組數(shù)據(jù)，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;
        }//合法區(qū)間設(shè)置為無窮大可婶，其他全部設(shè)置為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++)//設(shè)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個數(shù)有key和val沿癞，相鄰的并且key不互質(zhì)的兩個數(shù)可以消去并得到val，問最大價值和.
題解：狀態(tài)轉(zhuǎn)移有兩個來源扰肌，第一個是假若一個區(qū)間[i抛寝，j]里面的物品被抽光之后，而且key[i-1]和key[j+1]滿足題目條件的話曙旭，那么answer[i-1][i+1]=max(answer[i][j]+value[i]+value[j],answer[i][j]).假若在區(qū)間里面還剩下幾個不能被抽走盗舰，區(qū)間[i,j]的最大值就相當(dāng)于兩個區(qū)間直接拼在一起嘍answer[i][j]=max(answer[i][j],answer[i][k]+answer[k+1][j]).要判斷區(qū)間[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]，因?yàn)樵谒懊嬗衚-1個人嘛鳞绕，導(dǎo)演為了讓所有男屌的總不開心值最小失仁，搞了一個小黑屋，可以通過小黑屋來改變男屌的出場順
们何。這個小黑屋是個棧萄焦，男屌的順序是排好了的，但是可以通過入棧出棧來改變男屌的出場順序
那么對于dp[i][j]的第i個人，就有可能第1個上場拂封，也可以第j-i+1個上場茬射。考慮第K個上場
即在i+1之后的K-1個人是率先上場的冒签，那么就出現(xiàn)了一個子問題 dp[i+1][i+1+k-1-1]表示在第i個人之前上場的.對于第i個人在抛，由于是第k個上場的，那么憤怒值便是val[i](k-1).其余的人是排在第k+1個之后出場的萧恕，也就是一個子問題dp[i+k][j]刚梭，對于這個區(qū)間的人，由于排在第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堆石子排成一排，每堆石子有一定的數(shù)量《杷担現(xiàn)要將N堆石子并成為一堆磨德。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費(fèi)的代價為這兩堆石子的和吆视，經(jīng)過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]);
    }
}

石子合并 環(huá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乘積

設(shè)I是一個n位十進(jìn)制整數(shù)啦吧。如果將I劃分為k段您觉，則可得到k個整數(shù)。這k個整數(shù)的乘積稱為I的一個k乘積授滓。試設(shè)計一個算法琳水，對于給定的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的數(shù)字組成的10進(jìn)制數(shù)（包含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;
}