實機體驗,再天天抽M8三星平板★瘋殺5290起法人:14檔今年本業虧定了買太多也不行!7500...
2012-11-04 17:45:25 人氣(167) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[PTC][201210][搜索] Princess's Marriage

0
收藏
0
推薦


Sample Input

3
4 4 1 1 1 1
4 5 10 20 30 40 50
5 10 1 6 2 5 3 4 4 3 5 2

Sample Output
Congratulations
NO
Congratulations
2



#include <stdio.h>
int used[105] = {}, len;
int flag, m, n, w[105] = {};
void dfs(int idx, int now, int st, int sum) {
    if(flag)    return;
    if(sum > len)   return;
    if(sum == len) {
        dfs(0, now+1, 0, 0);
        return;
    }
    if(now == m) {
        flag = 1;
        return;
    }
    int i;
    if(st == 0) {
        for(i = 0; i < n; i++) {
            if(used[i] == 0) {
                used[i] = 1;
                dfs(i+1, now, 1, w[i]);
                used[i] = 0;
                break;
            }
        }
    } else {
        for(i = idx; i < n; i++) {
            if(used[i] == 0) {
                used[i] = 1;
                dfs(i+1, now, 1, sum+w[i]);
                used[i] = 0;
            }
        }
    }
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &m, &n);
        int sum = 0, i;
        for(i = 0; i < n; i++) {
            scanf("%d", &w[i]);
            sum += w[i];
        }
        if(sum%m) {
            puts("NO");
            continue;
        }
        len = sum/m, flag = 0;
        dfs(0, 0, 0, 0);
        if(flag)
            puts("Congratulations");
        else
            puts("NO");
    }
    return 0;
}

PTCPrincess'sMarriage
台長:Morris
人氣(167) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][三年後修訂] d371. 3. Huffman 編碼中的編碼效能問題
此分類上一篇:[ITSA] 18th 總解答

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文