Problem Solving►ZeroJudge

ZeroJudge d289 - 多元一次方程式

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

Solution

似背包問題，用 DP 求出每一個數有幾組解。

Code

ZJ d289ZJ d289
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#define N 8001

int main()
{
    int coe[8] = { 1, 13, 33, 43, 139, 169, 1309, 2597 };
    int i, j, dp[N] = {1}, n;
    for (i = 0; i < 8; i++)
        for (j = coe[i]; j < N; j++)
            dp[j] += dp[j - coe[i]];
    
    while (scanf("%d", &n) != EOF)
        printf("%d\n", dp[n]);

    return 0;
}