我做了个题目,但是测试过不了,大家看看
问题描述:Ztc想把他满屋子的书整理一下,为了应付繁重的学习任务,Ztc已经筋疲力尽了,于是向你求助,请你帮他计算他最少需要花费多少力气。
书本分成若干堆,呈直线排列。每一堆的书本都有重量W和价值V。Ztc的任务是将所有书本合成一堆。因为Ztc很看重书本的价值。所以他认为合并i,j两堆书本所需要的力气为Wi-Vi+Wj-Vj。合并后的书本的重量和价值均为合并前两堆书的重量和价值的总和。也就是说,合并i,j两堆书后W= Wi+Wj,V=Vi+Vj。
Ztc不愿意来回走,所以合并只能在相邻的两堆书间进行。书本合并前后,位置不变。如将1,2,3中1,2进行合并,那么合并结果为3,3,再将3,3合并为6(1,2,3,6表示重量)。
输入格式
第1行是1个整数n(2n400)。
第2..n+1行,每行有2个整数W和V(0<V<W1,000)。
输出格式
仅1行,1个整数f,表示最小力气。
样例输入输出:
book.in(这个能过)
3
6 5
9 7
11 2
book.out
15
我的代码:
程序代码:
#include <stdio.h> #define MAXL 400 //定义最大测资为400 struct book { long int w,v;//每一堆的书本都有重量W和价值V }book[MAXL]; //公式:合并i,j两堆书本所需要的力气为Wi-Vi+Wj-Vj。 long int strength=0,w_count,v_count=0;//strength为总合并重量,w_count为临时的w和变量,v_count为v和的临时变量 void print()//打印结果 { printf("%ld",strength); } void sorting_book(int n) { int i; for(i=0;i<n-1;i++)//循环n-1次 { if(i==0)//第一次初始化 { strength=strength+book[i].w-book[i].v+book[i+1].w-book[i+1].v;//将所有book的重量加起来 w_count=w_count+book[i].w+book[i+1].w;//将w两次的和加起来,第一次初值 v_count=v_count+book[i].v+book[i+1].v;//将v两次的和加起来,第一次初值 } else { strength=strength+w_count-v_count+book[i+1].w-book[i+1].v;//相加力气 w_count=w_count+book[i+1].w;//相加书的重量和价值 v_count=v_count+book[i+1].v;//相加书的重量和价值 } } } main() { int n,i;//n为有几堆书本 scanf("%d",&n);//输入有几堆书本 for(i=0;i<n;i++)//输入N堆书 scanf("%d %d",&book[i].w,&book[i].v);//用户输入数据 sorting_book(n);//将数据传入sorting_book中 print();//打印结果函数 }
再把样例发上来:
样例输入:
10
8 2
98 1
100 54
999 3
2 1
53 9
100 99
77 66
23 22
99 92
输出:
2673
样例输入:
100
1000 1
1000 999
1000 1
768 24
245 9
837 765
349 208
985 34
65 4
230 120
1000 1
1000 1
1000 999
1000 999
99 98
84 75
231 123
954 239
248 111
111 11
356 12
1000 1
1000 1
1000 999
1000 1
1000 353
1000 1
942 1
39 1
23 21
9 12
5 999
999 10
340 203
13 2
874 873
804 710
734 248
249 112
935 24
248 24
358 45
937 27
275 256
57 2
567 56
657 2
869 37
367 267
257 247
457 75
853 57
346 57
87 38
367 38
427 98
194 92
924 53
247 1
1000 99
1000 32
64 21
134 245
235 23
975 42
246 2
463 461
426 75
439 24
429 24
96 2
45 1
349 10
220 44
276 42
256 10
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
样例输出:
244533
数据大一点就过不了,大家帮我看看这个算法有什么问题。谢谢大家!