[NOIP2012]摆花

电玩女神 2024-03-24 11:02 53阅读 0赞

**早上把这题1a了**

**我 真 牛 逼**

题意：

![7088af96f1584b6c87e5afa4d4beac13.png][]

思路：

状态设计：

设dp\[i\]\[j\]\[k\]为前i种，已经选了j盆，该种选了k盆的方案数

i体现了阶段

j是为了有限制条件，一共只能m盆，属于影响决策的因素

k也是影响决策的因素，因为每种花能选的盆数有限

状态转移：

dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-k][z])%mod;

答案统计：

for(int k=0;k<=a[n];k++) ans=(ans+dp[n][m][k])%mod;

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=1e2+10;
    const int mxe=1e6+10;
    const int mod=1000007;
    int n,m;
    int a[mxn],dp[110][110][110];
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        dp[0][0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                for(int k=0;k<=a[i];k++){
                    for(int z=0;z<=a[i-1];z++){
                        if(j>=k) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-k][z])%mod;
                    }
                }
            }
        }
        int ans=0;
        for(int k=0;k<=a[n];k++) ans=(ans+dp[n][m][k])%mod;
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[7088af96f1584b6c87e5afa4d4beac13.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e4db347d42354cd8a73239c235091093.png

发表评论取消回复

表情：

评论列表（有 0 条评论，53人围观）

还没有评论，来说两句吧...

相关阅读

相关 [NOIP2012]摆花

早上把这题1a了我真牛逼题意： ![7088af96f1584b6c87e5afa4d4beac13.png][] 思路：状态设计：设dp\[i\]\

电玩女神/ 2024年03月24日 11:02/ 0 赞/ 54 阅读

相关【NOIp】NOIp2012

NOIp 2012 day 1 [T1 Vigenère 密码][T1 Vigen_re] 标签：模拟主要是用了ASCII码，字母'A'的ASCII码是41H（

我会带着你远行/ 2023年08月17日 16:49/ 0 赞/ 97 阅读

相关【NOIP2012】开车旅行

Description [【NOIP2012】开车旅行][NOIP2012] （题面太长不想描述……） Solution 由于题目很复杂，所以我们将这道题分成三

叁歲伎倆/ 2023年06月05日 08:55/ 0 赞/ 29 阅读

相关 NOIP2012 借教室线段树

[题目链接][Link 1] 看这道题的时候，题目中的借教室我们可以看作是区间修改，如果有一天不符合的话都不行，第一反应就是线段树，维护最小值，查询的时候看是否满足要求，满足

一时失言乱红尘/ 2023年06月04日 08:00/ 0 赞/ 18 阅读

相关输出正方形旋转摆花

这里写目录标题一、题目二、代码三、输出结果一、题目【题目描述】同学们弄来了不多于26种花，每种花有多盆。为使有限的鲜花摆放得更美

朴灿烈づ我的快乐病毒、/ 2023年02月14日 15:50/ 0 赞/ 55 阅读

相关 NOIP2012提高组开车旅行题解

题目连接：https://www.luogu.org/problem/show?pid=1081 题目描述：小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 1

「爱情、让人受尽委屈。」/ 2022年07月12日 03:17/ 0 赞/ 190 阅读

相关 NOIP 2012 质因数分解(数学)

题目描述已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。输入每组输入数据只有一行，包含一个正整数n。数据规模：对于60

比眉伴天荒/ 2022年05月17日 12:46/ 0 赞/ 371 阅读

相关 NOIP 2012 摆花(DP)

题目描述小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i

灰太狼/ 2022年05月16日 06:48/ 0 赞/ 163 阅读

相关 NOIP 2012初赛普及组C/C++答案详解

试题及答案 https://wenku.baidu.com/view/0d45c613657d27284b73f242336c1eb91b37335b.html 题解

ゝ一纸荒年。/ 2022年05月09日 04:24/ 0 赞/ 439 阅读

相关 NOIP2012国王游戏(贪心+高精度)

0701 国王游戏描述恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数

逃离我推掉我的手/ 2021年09月15日 23:02/ 0 赞/ 310 阅读