Barn Repair
第一章还没通关是一件很尴尬的事
这道题本来想用动归解得的，一来比较帅，二来好久没用过了，代码如下：
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!
roselone
2009年2月11日 00:45
我也做过这个，但是我没学过算法，用C写的，好像是贪心算法吧，哈哈。
2009年2月11日 21:40
用贪心应该更容易，时空效果也更佳！
2022年9月03日 02:00
Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. DPE Result Comilla The DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.
2023年7月19日 21:51
Students Should Download the Respective Stream wise MBOSE Board 7th Class Exam Syllabus Subjects of Hindi, English, Mathematics, Science, Social Science etc, Pdf Format Provide Check the same From our page here,Students need to Start Their Preparation by first Downloading the Stream wise MBOSE 7th Class Curriculum Syllabus 2024 Latest Edition.Meghalaya Board Class Syllabus 2024 is Designed in Meghalaya 7th Class Syllabus 2024 Accordance with the NCERT Based Guidelines and helps Students to get an Overview of the Hindi, English Medium All Subject, MBOSE keeps a Class Exam Pattern with the aim to Provide a Quality Education for All Students, On the basis of the Current Educational Demands
2024年1月08日 23:56
Board Model Papers 2024 provide all states of 6th to 10th text books 2024 Candidates who are Searching for 6th to 10th and 11th to 12th text books and syllabus, sample questions, exam pattern, and Co-Curricular Subject textbooks can refer to this entire article. boardmodelpaper.com and question papers for following the website and Arts, Science, Commerce Stream Subject Wise Solved Question Bank for Hindi & English Medium Students with Exam Pattern & Blueprint and subject Wise with 11th & 12th Question Bank 2024 for General & Vocational Course. Here, we have gathered all subjects of Board textbooks for all Class along with the direct download links.