洛谷P1622 釋放囚犯

題目描述

Caima王國中有一個奇怪的監獄，這個監獄一共有P個牢房，這些牢房一字排開，第i個緊挨著第i+1個（最後一個除外）。現在正好牢房是滿的。

上級下發了一個釋放名單，要求每天釋放名單上的一個人。這可把看守們嚇得不輕，因為看守們知道，現在牢房中的P個人，可以相互之間傳話。如果某個人離開了，那麼原來和這個人能說上話的人，都會很氣憤，導致他們那天會一直大吼大叫，搞得看守很頭疼。如果給這些要發火的人吃上肉，他們就會安靜點。

輸入輸出格式

輸入格式：

第一行兩個數P和Q，Q表示釋放名單上的人數；

第二行Q個數，表示要釋放哪些人。

【數據規模】

對於100%的數據1≤P≤1000； 1≤Q≤100；Q≤P；且50%的數據 1≤P≤100；1≤Q≤5

輸出格式：

僅一行，表示最少要給多少人次送肉吃。

輸入輸出樣例

20 3
3 6 14

35


【樣例說明】

先釋放14號監獄中的罪犯，要給1到13號監獄和15到20號監獄中的19人送肉吃；再釋放6號監獄中的罪犯，要給1到5號監獄和7到13號監獄中的12人送肉吃；最後釋放3號監獄中的罪犯，要給1到2號監獄和4到5號監獄中的4人送肉吃。




區間dp
dp[i][j]表示處理i,j這段區間內犯人的最小花費
轉移的時候枚舉一下斷點

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=1e3+10;
const int INF=0x7ffff;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin))?EOF:*p1++;
}
inline int read()
{
    char c=nc();int f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
    return x*f;
}
int a[MAXN],dp[MAXN][MAXN];
int DP(int l,int r)
{
    if(dp[l][r]!=-1)    return dp[l][r];
    dp[l][r]=INF;
    for(int k=l+1;k<=r-1;k++)
        dp[l][r]=min(dp[l][r],DP(l,k)+DP(k,r)+a[r]-a[l]-2);
    return dp[l][r];
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int n=read(),m=read();
    for(int i=1;i<=m;i++)   a[i]=read();
    a[0]=0;a[m+1]=n+1;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=n;i++) dp[i][i+1]=0;
    printf("%d",DP(0,m+1));
    return 0;
}