题解：P11246 [GESP202409 六级] 小杨和整数拆分

· · 题解

洛谷P11246[GESP202409六级] 小杨和整数拆分

一道很简单的动态规划题目。

思路

感觉全题的难点在于推转移方程。

看一眼数据范围只是普通的 10^5 啊。

那么跑两层循环 ,外层跑 1\sim n 内层跑完全平方数。复杂度最差也只是朴素的 O(n\sqrt{n}) 呗,完全够水完成这题了。

考察

或许这方程是唯一难点。普通的完全背包。我们把最大价值更换为最少用到的数理解即可。 每一次的状态是分和不分完全平方数。

dp[i] = min(dp[i], dp[i - j * j] + 1);

AC代码

AC代码如下:

(题目中的 n 为正整数。 1 就是一个完全平方数。但是为了保险还是初始化了 dp[0] 的情况,此时没有完全平方数)。

#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 1e5 + 10;
int dp[MAXN]; 
int solve(int n) 
{
    dp[0] = 0;//初始化 
    for (int i = 1 ; i <= n ; ++i) 
    {
        for (int j = 1 ; j * j <= i ; ++j)
        {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }

    return dp[n];
}
int main() {
    memset(dp,n+1,sizeof(dp));//初始化一下dp数组的值 因为需要求min的值 所以将dp[]的值往大了放 
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}