Problem Solving►UVa

UVa 11407 - Squares

Contents

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

Problem

題目網址
中文網址

注意同樣數字，重複出現仍算不同項。

Solution

建完表後做 DP，像背包問題。

Code

UVa 11407UVa 11407 - Squares
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 101
#define M 10001

int main()
{
    int dp[M] = {};
    int square[N] = {}, i, j;

    for (j = 1; j < M; ++j)
        dp[j] = 10001;

    for (i = 1; i < N; ++i)
        square[i] = i*i;

    for (i = 1; i < N; ++i)
        for (j = square[i]; j < M; ++j)
            dp[j] = MIN(dp[j - square[i]] + 1, dp[j]);

    int n,Case;
    scanf("%d", &Case);
    while (Case--)
    {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }

    return 0;
}