Barn Repair

roselone posted @ 2009年2月10日 21:53 in USACO征程 with tags usaco Barn Repair , 1213 阅读

第一章还没通关是一件很尴尬的事

 

这道题本来想用动归解得的,一来比较帅,二来好久没用过了,代码如下:

/*
ID: roselone
LANG: C++
TASK: barn1
*/


//动态规划求解,
//将有牛的牛棚排序后,设置一个函数d[i,j]表示第i个牛修到第j个牛需要使用的木版长度,设f[i,j]表示用前i个木版修到第j头牛所用的最短长度.
//f[i,j]=min{f[i-1,k]+d[k,j]}; (i<=k<=j)
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>

using namespace std;
int d[201][201];
int f[51][201];
int m,s,c;
int a[51];
ifstream fin("castle.txt");
ofstream fout("barn1.out");
bool cmp(int a,int b)
{
        return (a<b);
}

void init()
{
        fin>>m>>s>>c;
        for (int i=1;i<=c;i++)
                fin>>a[i];
        sort(a+1,a+c+1,cmp);
        for (int i=1;i<=c;i++)
        {       d[i][i]=1;
        f[i][i]=i;}
        for (int i=1;i<=c;i++)
                {f[1][i]=a[i]-a[1]+1; }
        for (int i=1;i<c;i++)
                for (int j=i+1;j<=c;j++)
                        d[i][j]=a[j]-a[i]+1;
}

int main()
{
        init();
        for (int i=2;i<=m;i++)
                for (int j=i;j<=c;j++)
                {  f[i][j]=220;
                        for (int k=i;k<=j;k++)
                        {
                                int temp=f[i-1][k-1]+d[k][j];
                                if (temp<f[i][j]) f[i][j]=temp;
                        }
                }
        if (m>=c) fout<<c<<endl;
        else
        cout<<f[m][c]<<endl;                               
        return 0;
}

 

 

编译没问题,前几个测试数据也顺利通过了,但是第5个竟奇迹般的出现运行时错误,被迫中止,郁闷啊……

调试,再调试……

咦?越界么?

原来是数组a开的太小了,应该用c的最大值,又是题目没看清,改成a[201]后~~AC~!

 

 USER: rose lone [roselon2]
TASK: barn1
LANG: C++

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.011 secs, 3044 KB]
Test 2: TEST OK [0.022 secs, 3040 KB]
Test 3: TEST OK [0.011 secs, 3040 KB]
Test 4: TEST OK [0.000 secs, 3044 KB]
Test 5: TEST OK [0.000 secs, 3040 KB]
Test 6: TEST OK [0.022 secs, 3040 KB]
Test 7: TEST OK [0.011 secs, 3040 KB]
Test 8: TEST OK [0.011 secs, 3040 KB]
Test 9: TEST OK [0.000 secs, 3040 KB]
Test 10: TEST OK [0.011 secs, 3040 KB]

All tests OK.

Your program ('barn1') produced all correct answers! This is your
submission #5 for this problem. Congratulations!

Avatar_small
xiaoee 说:
2009年2月11日 00:45

我也做过这个,但是我没学过算法,用C写的,好像是贪心算法吧,哈哈。

Avatar_small
roselone 说:
2009年2月11日 21:40

用贪心应该更容易,时空效果也更佳!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter