【Gym - 101002F】Mountain Scenes（dp）

时间：2025-04-25 21:33:50

Mountain Scenes

Descriptions

给你一个长度为n的丝带，一个宽w一个高h 的 格子，用丝带去填充格子，这填充后只需要满足至少有一列的丝带长度与其他格子不同即可。丝带可以不全部用上，格子可以不放丝带，只要有一列的丝带长度不同则这种放法就与其他方案不同。问一共有多少种放放法。

Sample Input1

25 5 5

Sample Output 1

7770

Sample Input 2

15 5 5

Sample Output 2

6050

Sample Input 3

10 10 1

Sample Output 3

1022

Sample Input 4

4 2 2

Sample Output 4

6

题目链接

https://vjudge.net/problem/Gym-101002F

dp[i][j]代表到第i列为止用了j米长的情况数，下一状态等于前一状态的各种情况的总和

代码中有几点要解释一下   tmp=n/w+1 求的是按宽绳子全用铺平，看能铺几层 再加上 0这一层

　　　　　　　　　　　　h+1 求的是按高来铺绳子，能铺h+1层

　　　　　　　　　　　　min(tmp,h+1) 求的是最终能铺几层

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 10000+10

using namespace std;

ll n,w,h;

ll dp[][Maxn];

int main()

{

    cin>>n>>w>>h;

    MEM(dp,);

    dp[][]=;

    for(int i=; i<=w; i++)//枚举列

        for(int j=; j<=n; j++)//枚举到前一列为止用了多少绳子

            if(dp[i-][j])//前一次更新过才能更新下一个

            {

                for(int k=; k<=h; k++)//枚举这一列的高度

                {

                    if(j+k>n)//高度超过总绳长就不行

                        break;

                    dp[i][j+k]=(dp[i][j+k]+dp[i-][j])%Mod;

                }

            }

    ll tmp=n/w+;

    ll ans=;

    for(int i=;i<=n;i++)

        ans=(ans+dp[w][i])%Mod;

    cout<<(ans-min(tmp,h+)+Mod)%Mod<<endl;

    return ;

}

相关文章