syhd142  
日历
<2010年11月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011
统计
  • 随笔 - 23
  • 文章 - 122
  • 评论 - 31
  • 引用 - 0

导航

常用链接

留言簿(2)

随笔档案(23)

文章分类(270)

文章档案(122)

我的豆瓣

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
题目大意:将一段木棒按要求切割,每次切割都要付出与木棒长度相同的代价,求最小代价切割。
状态表示:d[x][y]表示[x,y]区间上切割所用的最小值,转移方程:d[x][y]=min{d[x][a[i]]+d[a[i]][y]+(y-x)|a[i]为[x,y]内的切割点}
#include <stdio.h>
#include 
<string.h>

#define N 55
#define INF 1 << 29
#define MIN(a, b) (a < b ? a : b)

int a[N], c[N][N];

int main()
{
    
int l, n, d;
    
while(scanf("%d"&l), l)
    {
        scanf(
"%d"&n);
        
for(int i = 1; i <= n; i++)
            scanf(
"%d"&a[i]);
            
        a[
0= 0, a[n + 1= l;
        
for(int i = 0; i <= n; i++)
            c[i][i 
+ 1= 0;
        
        
for(int i = 1; i <= n + 1; i++)
        {
            
for(int j = i - 2; j >= 0; j--)
            {
                d 
= INF;
                
for(int k = j + 1; k < i; k++)
                    d 
= MIN(d, c[j][k] + c[k][i]);
                c[j][i] 
= d + a[i] - a[j];
            }
        }
        printf(
"The minimum cutting is %d.\n", c[0][n + 1]);
    }
    
return 0;
}
posted on 2010-06-18 01:05 Fucker 阅读(308) 评论(1)  编辑 收藏 引用 所属分类: ACM/ICPCDP
评论:
  • # re: UVA 10003 Cutting Sticks  jerrymu1234 Posted @ 2010-11-17 14:01
    请教楼主:

    如何在求minimum cost值的同时,
    记录所cut的点的次序??被困扰好久。。。。。

    比如input:
    10 (木棍长)
    3 (切3次)
    2 4 7 (在2,4,7处切)
    Output:
    The minimum cost is 20.
    The optimal cutting sequence: 4,2,7  回复  更多评论   


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


 
Copyright © Fucker Powered by: 博客园 模板提供:沪江博客