hrb 1476 动态规划

题意:

　　n个单词，每行字符数量m个，单行字符数量值为j时，花费我 (m-j)^3

　　单词间有一个空格，问最小花费。 最后一行不花费

解法

　　dp[i][j] 表示前i个单词，长度为j的最小花费

　　

// 最后一行多余空格不作为计算，只有出现换行时才计算。

// dp[i][j] 表示前i个单词，长度为j的最小整齐度
// 由 dp[i][j] 通过添加一个 单词 L[i+1] 只可能导致两种情况
// 1, 依然在一行,此时应满足条件
// 若 j == 0 ，则此时必定可以添加到后面有
// dp[i+1][ L[i+1] ] = Min{ dp[i][j] }
// 若 j > 0 , 则此时需满足 j+1+L[i+1] 有
// dp[i=1][ j+1+L[i+1] ] = Min{ dp[i][j] }
// 2, 若换行，此时应满足条件 j > 0
// dp[i+1][ L[i+1] ] = Min{ dp[i][j] + (M-j)^3 }

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define cmp(x) (x)*(x)*(x)
typedef unsigned long long LL;
const LL inf = ~0u>>1;
// 最后一行多余空格不作为计算，只有出现换行时才计算。 

// dp[i][j] 表示前i个单词，长度为j的最小整齐度
// 由 dp[i][j] 通过添加一个 单词 L[i+1] 只可能导致两种情况
//        1, 依然在一行,此时应满足条件     
//            若 j == 0 ，则此时必定可以添加到后面有
//                dp[i+1][ L[i+1] ] = Min{ dp[i][j] }
//            若 j  > 0 , 则此时需满足 j+1+L[i+1] 有 
//                 dp[i=1][ j+1+L[i+1] ] = Min{ dp[i][j] }
//        2, 若换行，此时应满足条件 j > 0
//            dp[i+1][ L[i+1] ] = Min{ dp[i][j] + (M-j)^3 } 
LL dp[2][510];
int L[2010];
int n, m;
void DP(){
//    memset( dp, 0xff, sizeof(dp) );
    for(int i = 0; i < m; i++) dp[0][i] = inf;
    dp[0][0] = 0;
    for(int i = 0; i < n; i++){
        int cur = i&1, nxt = (i+1)&1;
        for(int j = 0; j < m; j++) dp[nxt][j] = -1; 
        for(int j = 0; j < m; j++){
            if( (dp[cur][j] != -1)   ){ 
                if( j == 0 ){
                    int len = (j+L[i+1] == m )? 0 : j+L[i+1];
                //    if( dp[nxt][len] == -1 ) dp[nxt][len] = dp[cur][j];
                //    else dp[nxt][len] = min( dp[nxt][len], dp[cur][j] );    
                    dp[nxt][len] = min( dp[nxt][len], dp[cur][j] );
                }
                else if( j+1+L[i+1] <= m ){
                    int len = (j+1+L[i+1] == m) ? 0 : j+1+L[i+1];
                    if( len < m ){
                    //    if( dp[nxt][len] == -1 ) dp[nxt][len] = dp[cur][j];
                    //    else dp[nxt][len] = min( dp[nxt][len], dp[cur][j] );    
                        dp[nxt][len] = min( dp[nxt][len], dp[cur][j] );
                    }
                }  
                if( j > 0 ){
                //    if( dp[nxt][ L[i+1] ] == -1 ) 
                //        dp[nxt][ L[i+1] ] = dp[cur][j] + cmp(m-j);
                //    else
                        dp[nxt][ L[i+1] ] = min( dp[nxt][ L[i+1] ], dp[cur][j] + cmp(m-j) );
                }
            } 
        }     
    } 
    LL ans = inf;
    for(int i = 0; i < m; i++){
        if( dp[ n&1 ][i] != -1 ){
            if( ans == -1 ) ans = dp[n&1][i];
            else ans = min( ans, dp[n&1][i] );    
        } 
    }
    printf("%llu\n", ans );
}

int main(){
    while( scanf("%d%d", &n,&m) != EOF){
        for(int i = 1; i <= n; i++)
            scanf("%d", &L[i] );
        DP();    
    } 
    return 0;    
}