misschuer

常用链接

统计

积分与排名

百事通

最新评论

hdu 1500 Chopsticks

http://acm.hdu.edu.cn/showproblem.php?pid=1500
#include <iostream>
using namespace std;

int dp[ 5001 ][ 1600 ];

int min(int a , int b)
{
    return a < b ? a : b;
} 

int main()
{
    int t , k , n , i , j;
    
    int b[ 5001 ] , a[ 5001 ];
    
    cin >> t;
    
    while (t --)
    {
        cin >> k;
        
        cin >> n;
        
        for(i = 1 ; i <= n ; ++ i)
            
            cin >> a[ i ];
        
        for(i = 1 ; i < n ; ++ i)
            
            b[ i ] = (a[ i ] - a[i + 1]) * (a[ i ] - a[i + 1]);
        
        for(i = 0 ;i <= n; ++ i)
            
            for(j = 0 ; j <= 8 + k ; ++ j )
                
                dp[ i ][ j ] = 987654321;
            
            for(i = 0 ; i <= n; ++ i)
                
                dp[ i ][ 0 ] = 0;
            
            
            for(i = n - 2 ; i >= 1 ; -- i)
                
                for(j = 1 ; 3 * j <= ( n - i + 1 ); ++ j)
                {
                    
                    dp[ i ][ j ] = min( dp[ i + 2 ][j - 1] + b[ i ] , dp[ i + 1 ][ j ] );
                    
                }
                
                printf ("%d\n" , dp[ 1 ][k + 8]);
                
                
    }
    
    return 23;
}

posted on 2009-04-19 13:34 此最相思 阅读(465) 评论(0)  编辑 收藏 引用 所属分类: dp


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理