題目描述 Caima王國中有一個奇怪的監獄,這個監獄一共有P個牢房,這些牢房一字排開,第i個緊挨著第i+1個(最後一個除外)。現在正好牢房是滿的。 上級下發了一個釋放名單,要求每天釋放名單上的一個人。這可把看守們嚇得不輕,因為看守們知道,現在牢房中的P個人,可以相互之間傳話。如果某個人離開了,那麼原 ...
題目描述
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
輸出格式:
僅一行,表示最少要給多少人次送肉吃。
輸入輸出樣例
輸入樣例#1: 複製20 3 3 6 14輸出樣例#1: 複製
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; }