摘要
Title: 3072. 减肥
Tag: 整数划分、计数dp、dp
Memory Limit: 64 MB
Time Limit: 1000 ms

3072. 减肥

题意

小明是一个大胖子，为了让体重达到正常水平，他的计划是：减掉 n 千克体重，分多周完成(至少是 2 周)，每周都减重正整数千克。为了激励自己，他决定每周减掉的体重都必须比上周减掉的体重多。假设他上周减重 0 千克，他从这周开始执行计划，请问可以设计出多少种方案？
思路

其实就相当于整数划分问题，将n划分为互不相同的k个数，而以往的是可以相同
所以dp方程有所变化

$dp[i][j] = dp[i - j][j] + dp[i - j][j - 1]$
- 当最小值为1时，每个数都减1，那么总数为i-j，还有j-1个数
  - 之前是dp[i - 1][j - 1], 是因为只是1减去了1，不能所有都减1，因为不能确定1有几个
- 当最小值不是1，每个数都减1，那么总数为i-j，还有j个数

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-06-09 21:17:06
* @FilePath: \LanQiao\3072\3072.cpp
* @LastEditTime: 2023-06-09 21:38:56
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 510, INF = 0x3f3f3f3f;
int dp[N][N], res;

int f(int n)
{
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
            dp[i][j] = dp[i - j][j] + dp[i - j][j - 1];
    }
    int ans = 0;
    for (int i = 2; i <= n; ++i)
    {
        ans += dp[n][i];
    }
    return ans;
}
signed main()
{
    IOS;
    int n;
    cin >> n;
    cout << f(n) << '\n';
    return 0;
}

3072. 减肥

题意

思路

代码