NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 C.節約尺

作者 主題: NPSC 2005 高中組 決賽 C.節約尺  (閱讀 2267 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 242
    • 檢視個人資料
NPSC 2005 高中組 決賽 C.節約尺
« 於: 十二月 08, 2009, 02:32:23 pm »

NPSC 2005 高中組 決賽 C.節約尺

說明:假設一把長度為 L 的尺將其分成 N 段(每一段都是整數),如果從 1 到 L 的任意一個整數都可以從某幾段相鄰的片段組成,則這把尺就是節約尺。

解法:利用暴力法,將所有相鄰片段可以組成的長度都算出來,看是不是可以組合出 1 到 L 之間所有的整數。要注意 L==N 的例外情況。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2005 決賽 - 題目 C - 節約尺 //
#include <iostream>
#include <fstream>
#include <cstdlib>
#define MAX 400
#define N 20

using namespace std;

int sec[N], mark[MAX];

int main()
{
    ifstream fin("pc.in");
    ofstream fout("pc.out");
    int n, total, len, save, i, j;
   
    while (1)
    {
        fin >> n;
        if (!n) break;
        for (i=0, total=0; i<n; i++)
        {
            fin >> sec[i];
            total+=sec[i];
        }
        if (total == n)
        {
            fout << "NO" << endl;
            continue;
        }
        for (i=1; i<=total; i++)
            mark[i]=0;
        for (i=0; i<n; i++)
        {
            for (j=i, len=0; j<n; j++)
            {
                len+=sec[j];
                mark[len]=1;
            }
        }
        for (i=1, save=1; i<=total; i++)
            if (mark[i]==0)
            {
                save=0;
                break;
            }
        if(save) fout << "YES" << endl;
        else fout << "NO" << endl;
    }
   
//    system("PAUSE");
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 C.節約尺