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 此最相思 阅读(423) 评论(0)  编辑 收藏 引用 所属分类: dp


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