试题描述： NOIP 王国有一个奇怪的监狱，这个监狱一共有 P 个牢房，这些牢房一字排开，第 i 个 紧挨着第 i+1 个（最后一个除外）。现在正好这个牢房是满的。 上级下发了一个释放名单，要求每天释放名单上的一个人。这可把看守WSM吓得不轻， 因为WSM知道，现在牢房中的 P 个人，可以相互之间传话。如果某个人离开了，那么原来 和这个人能说上话的人，都会非常气愤，导致他们那天会一直大吼大叫，搞得WSM很头疼。 如果给这些要发火的人吃上肉，他们就会安静点。 现在WSM想知道，如何安排释放顺序，才能使他们花费的肉钱最少。 输入格式： 第一行两个数 P 和Q，Q表示释放名单上的人数。 第二行Q个数，表示要释放哪些人。 输出格式： 仅一行，表示最少要给多少人次送肉吃。 数据规模： 1<=P<=1000；1<=Q<=100。 输入样例： 20 3 3 6 14 输出样例： 35 注意事项： Q<=P；且 50%的数据 1<=P<=100；1<=Q<=5。
题解:
对于50%的数据，枚举释放顺序即可。 如果一个区间[x,y]中所有人都还在，现在区间中的z先被释放，代价就(y-x)(总数-1)，且一旦z被释放，则区间变成了两个[x,z-1]和[z+1,y]，此时释放其他的人，所支付的代价就之和这两个区间有关系了，且两个区间中的不同释放顺序是不会互相影响。 于是很容易想到基于这个区间的动态规划。 用f[i,j]表示在[i,j]区间所有该被释放的人都被释放的最小支付代价。很显然，需要枚举里面的哪个人最先被释放。假设释放了k，则代价就是f[i][k-1]+f[k+1][j]+(j-i)。动态规划转移就是f[i,j]=max{f[i][k-1]+f[k+1][j]+(j-i)}。 很显然动态规划的复杂度是O(P2Q)。这个复杂度就能通过本题的数据了。动态规划所涉及的值，它只和需要被释放人的序号ki以及ki±1有关。动态规划时只要考虑Q个状态就行了。这样复杂度就是：O(Q3) 上述算法的效率已经很高了，但是还可以优化。利用四边形不等式，可以把动态规划的复杂度优化到O(1)，整体复杂度就是：O(Q2)。
时间复杂度：O(P^2Q) | O(Q^3) | O(Q^2) 空间复杂度：O(P^2) | O(Q^2)
代码：
#include<bits/stdc++.h> #define F(i,a,b) for( int i=(a);i<=(b);i++ ) #define N 1001 #define M 10001 #define LL long long #define oo 0x7fffffff using namespace std; int read() { int f=1,s=0; char ch=getchar(); while( ch>'9' || ch<'0' ) { if( ch=='-' ) f=-1; ch=getchar(); } while( ch<='9' && ch>='0' ) { s=( s<<1 )+( s<<3 )+ch-'0'; ch=getchar(); } return f*s; } int m,n,k; int tot,cnt,ans; int p,q; int a[N],low[N]; int d[N][N]; int dp( int l,int r ) { if( d[l][r] ) return d[l][r]; d[l][r]=oo; F( i,low[l],q ) { k=a[i]; if( k>r ) break; else d[l][r]=min( d[l][r],dp( l,k-1 )+dp( k+1,r )+r-l ); } if( d[l][r]==oo ) d[l][r]=0; return d[l][r]; } int main() { //freopen( ".in","r",stdin ); //freopen( ".out","w",stdout ); p=read(); q=read(); F( i,1,q ) a[i]=read(); sort( a+1,a+n+1 ); int t=1; F(i,1,p) { low[i]=t; if( i==a[t] ) t++; } cout<<dp( 1,p )<<endl; return 0; }