题意是，给出n个点对(xi, ci)，划分成若干段，每段[i..j]的代价是ci+{sum(xk-xi),i<=k<=j}。问说如何划分使得代价最小。
用DP，枚举第m+1段中的第m段，然后dp[i] =min{ dp[j] + cost(i, j) }，转移的复杂度是O(n)，状态的复杂度是O(n)，总复杂度是O(n^2)，不过用上类似单调队列优化的多重背包问题，可以把这题的复杂度优化到O(n)的。
代码 #include < iostream > #include < string > #include < stdio.h > #include < stdlib.h > #include < algorithm > #include < string .h > #include < vector > #include < math.h > #include < map > #include < time.h > #include < queue > #include < set > using namespace std;typedef __int64 int64; const int MAX = 3005 ; int n;int64 cost[MAX][MAX];int64 dp[MAX]; struct NODE{ int x, c; NODE() {} NODE( int _x, int _c) : x(_x), c(_c) {} bool operator < ( const NODE & t) const { return x < t.x; }}node[MAX]; void ready(){ // make the cost memset(cost, 0 , sizeof (cost)); for ( int i = 1 ; i <= n; i ++ ) for ( int j = i + 1 ; j <= n; j ++ ) { cost[i][j] = cost[i][j - 1 ] + node[j].x - node[i].x; // printf("%d->%d %d\n", i, j, cost[i][j]); }}int64 go(){ for ( int i = 1 ; i <= n; i ++ ) dp[i] = 1LL << 60 ; dp[ 0 ] = 0 ; for ( int i = 1 ; i <= n; i ++ ) { for ( int k = 0 ; k <= i - 1 ; k ++ ) { int64 t = dp[k] + cost[k + 1 ][i] + node[k + 1 ].c; if (t < dp[i]) dp[i] = t; } } return dp[n];} int main(){ while (scanf( " %d " , & n) != EOF) { for ( int i = 1 ; i <= n; i ++ ) scanf( " %d%d " , & node[i].x, & node[i].c); sort(node + 1 , node + n + 1 ); ready(); printf( " %I64d\n " , go()); }} /* 32 33 41 241 73 15 106 1 */
转载于:https://www.cnblogs.com/litstrong/archive/2010/11/02/1866870.html
