蓝桥杯/减肥/c\c++

问题描述

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

输入格式

    第一行输入n , 表示小明计划减掉的体重

输出格式

    输出仅一行，包含一个整数，表示答案

样例输入

3

样例输出

1

每周减掉的体重都必须比上周减掉的体重多，要减去3千克，只存在1个方案：即第一周减去1kg，第二周减2kg.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=502; 
int n;
ll dp[N][N];//dp[i][j]表示总共减肥i千克,本周减肥j千克的方案数 
ll ans;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)//枚举所有可能的总共减肥千克数i 
    {
        dp[i][i] = 1;//总共减肥i千克,本周减肥i千克,只有一种方案 
        for (int j = 1; j < i; j++)//枚举所有可能的本周减肥千克数j 
        {
            for (int k = 0; k < j && j + k <= i; k++)//枚举上一周所有可能的减肥千克数k 
            {
                //若要在本周减肥j千克,总共减肥i千克,则应该在一周前总共减肥i-j千克,上一周减肥k千克
                //k的范围是[0,i-j],累加所有的dp[i-j][k]即可 
                dp[i][j] += dp[i - j][k];
            }
        }
    }
    for (int j = 0; j < n; j++)//总共减肥n千克,枚举本周所有可能的减肥千克数0~n-1 
    {
        ans += dp[n][j];
    }
    //由于不能一周减完,因此不统计dp[i][i] 
    cout << ans << endl;
    return 0;
}