NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2004高中組初賽
 NPSC 2004 高中組 初賽 B.骨牌遊戲

作者 主題: NPSC 2004 高中組 初賽 B.骨牌遊戲  (閱讀 1861 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 243
    • 檢視個人資料
NPSC 2004 高中組 初賽 B.骨牌遊戲
« 於: 十二月 08, 2009, 03:39:45 pm »

NPSC 2004 高中組 初賽 B.骨牌遊戲

說明:給你 N 個 1~1000 的正整數 s1 ~ sn,請你依照原本的順序,將它們分成 w+1 組並各自算出其數字和,請問你要如何分組,才能讓數字和最大的那一組的數字和儘可能的小。

解法:使用動態規劃(Dynamic Programming,DP)。假設 s[ i ][j] 為前 j 個數分成 i+1 組(也就是放入 i 個重骨牌)時數字和最大的那一組的值。s[0][1] ~ s[0][n] 則是前 n 個數的和(全部在同一組)。假說最後一組是從第 k 個數字後面開始,則這時最大的數字和為 s[i-1][k] 和 s[0][j]-s[0][k] (也就是 sk+....+sj 的和)兩者較大的那個。我們讓 k 從 j-1 一直往前到 i-1 的位置,各別求出其 max( s[0][j]-s[0][k], s[i-1][k] ),取最小的那個,即可得到 s[ i ][j] 的值。也就是:

for i=1 to w, for j=i to n
s[ i ][j] = min( max( s[0][j]-s[0][k], s[i-1][k])  k=j-1 to i-1 )

另外,如果 s[0][j]-s[0][k]  比之前找到的最小值來得大,就可以不用再找下去了,以免浪費時間。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2004 初賽 - 題目 B - 骨牌遊戲 //
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#define MAX 1002

using namespace std;

int s[MAX][MAX];

int main()
{
    ifstream fin("pb.in");
    ofstream fout("pb.out");
    int n, w, m, i, j, k, t;

    s[0][0]=0;
    while (1)
    {
        fin >> n >> w;
        if ( n==0 && w==0 ) break;
        for (i=1; i<=n; i++)
        {
            fin >> t;
            s[0][i]=s[0][i-1]+t; // 輸入的同時做累加
        }
        for (i=1; i<=w; i++)
        {
            for (j=i; j<=n; j++)
            {
                for (k=j-1, m=s[0][n]; k>=i-1; k--)
                {
                    t=s[0][j]-s[0][k];
                    if ( t>m ) break;
                    t=max(t, s[i-1][k]);
                    if ( t<m ) m=t;
                }
                s[i][j]=m;
            }
        }
        fout << s[w][n] << endl;
    }

//    system("PAUSE");
    return 0;
}
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 243
    • 檢視個人資料
二分搜尋+Greedy解
« 回覆 #1 於: 十二月 08, 2009, 03:40:34 pm »

二分搜尋+Greedy解

提供者:su_horng

解法:轉變一下題目, 如果我們規定傷害值不能超過x, 可以Greedy求出最少需要幾個重骨牌.
只要對x值做二分搜, 即可求出答案.

參考程式:(By su_horng)

代碼: [選擇]
#include <cstdio>

int N, K, C[1000];

int findMin(int limit) {
  int i, sum = 0, sec = 1;
  for (i=0; i<N && sec<=K; i++) {
    sum += C[i];
    if (sum > limit) {
      sum = C[i];
      sec ++;
    }
  }
  return sec;
}

int main() {
  int i, L, R, l, m, r, k;
  while (scanf("%d%d", &N, &K) && N) {
    L = R = 0; K ++;
    for (i=0; i<N; i++) {
      scanf("%d", C+i);
      R += C[i];
      if (C[i] > L) L = C[i];
    }
    l = L, r = R;
    while (l <= r) {
      m = (l+r)/2;
      k = findMin(m);
      if (k > K) {
        l = m+1;
      } else if (k <= K) {
        r = m-1;
      }
    }
    while (findMin(m) > K) m ++;
    while (m>L && findMin(m-1)<=K) m--;
    printf("%d\n", m);
  }
  return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2004高中組初賽
 NPSC 2004 高中組 初賽 B.骨牌遊戲