USACO的Greedy Algorithm說明文寫得根本不是Greedy Algorithm……
什麼求n = 5時先求n = 4的最佳解,害我想到DP去。
(因為n = 4的最佳解必定是n = 3的最佳解……根本就是從n = 1往上推的意思)
如果演算法正確還ok,
問題是DP的code到測資第5組就gg惹 =.=。
你說這不會讓人想殺人嗎?
其實也不用管什麼Greedy不Greedy的,
直接想作法還比較實際……
Greedy Algorithm這名詞真是抽象無比。
先對C做sort。
接著算出每個C之間的間距,一樣sort。
再計算只用1塊板子的長度Len,
當m = 1表示用1塊板子,Len就是答案。
m = 2時,Len要減去最大間距,
m = 3時,Len要減去最大間距與次大間距。
若m >= C,直接output C。
其實就這樣而已……
另外fopen本來就要fclose吧?
USACO的code從不做fclose,
無言。
盡信書不如無書。
一堆google別人想的解法還比USACO的好太多了 = =。
/* ID: mythnc2 LANG: C TASK: barn1 barn repair 2011/11/16 16:21:20 */ #include <stdio.h> #include <stdlib.h> #define MAXARY 200 int cmp(const void *, const void *); int main (void) { FILE *fin, *fout; int n, nc, i, sum; int ary[MAXARY], diff[MAXARY]; fin = fopen("barn1.in", "r"); fout = fopen("barn1.out", "w"); fscanf(fin, "%d %*d %d", &n, &nc); for (i = 0; i < nc; i++) fscanf(fin, "%d", ary + i); if (n < nc) { qsort(ary, nc, sizeof(int), cmp); for (i = 0; i < nc - 1; i++) diff[i] = ary[i + 1] - ary[i] - 1; qsort(diff, nc - 1, sizeof(int), cmp); sum = ary[nc - 1] - ary[0] + 1; for (i = nc - 2; n > 1 ; i--, n--) sum -= diff[i]; fprintf(fout, "%d\n", sum); } else fprintf(fout, "%d\n", nc); fclose(fin); fclose(fout); return 0; } /* cmp: function of qsort argument */ int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
沒有留言:
張貼留言