第十三届蓝桥杯C++B组省赛 I 题——李白打酒加强版 (AC)
admin
2024-04-07 11:50:57
0次

目录

  • 1.李白打酒加强版
    • 1.题目描述
    • 2.输入格式
    • 3.输出格式
    • 4.样例说明
    • 5.数据规模
    • 6.原题链接
  • 2.解题思路
  • 3.Ac_code

1.李白打酒加强版

1.题目描述

话说大诗人李白, 一生好饮。幸好他从不开车。

一天, 他提着酒壶, 从家里出来, 酒壶中有酒 2 斗。他边走边唱:

无事街上走,提壶去打酒。 逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 NNN 次, 遇到花 MMM 次。已知最后一次遇到的是花,他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

注意: 壶里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。

2.输入格式

5 10

3.输出格式

14

4.样例说明

如果我们用 0 代表遇到花,1 代表遇到店,14 种顺序如下:

010101101000000

010110010010000

011000110010000

100010110010000

011001000110000

100011000110000

100100010110000

010110100000100

011001001000100

100011001000100

100100011000100

011010000010100

100100100010100

101000001010100

5.数据规模

1≤N,M≤1001≤N,M≤1001≤N,M≤100

6.原题链接

李白打酒加强版

2.解题思路

比较明显是一道状态机dp的题目,如何定义好状态可以帮助我们更好地初始化和转移以及求解答案,根据题目范围最大为100,比较明显暗示我们做法是一个O(n3)O(n^3)O(n3)的dp,dp状态也应该是三维的。定义状态f[i][j][k]f[i][j][k]f[i][j][k] 为已经遇到 iii 次店,jjj次花,还剩 kkk 斗酒的方案数。状态初始化明显是f[0][0][2]=1。

对于酒的上限数量,我们应该想好范围,因为花最多只有 mmm 朵,意味着我们最多只能喝 mmm 壶酒,对于 kkk 超过 mmm 的状态都是无效状态我们无需关心。所以剩余酒的上限也就是 kkk 应该也定为 mmm 。

考虑进行状态转移,对于状态f[i][j][k]f[i][j][k]f[i][j][k],假设最后一次遇到的是店,那么此时需要保证 iii 大于0,并且 kkk 是偶数,因为遇到店剩余酒翻倍,kkk 一定不可能为奇数,那么可以得到转移方程
f[i][j][k]=(f[i][j][k]+f[i−1][j][k/2])%modf[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) \% modf[i][j][k]=(f[i][j][k]+f[i−1][j][k/2])%mod

假设最后一次遇到的是花,那么此时只需要保证 jjj 大于 0即可,我们可以获得转移方程f[i][j][k]=(f[i][j][k]+f[i][j−1][k+1])%modf[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) \% modf[i][j][k]=(f[i][j][k]+f[i][j−1][k+1])%mod

我们还得考虑答案输出什么,题目要求最后一次遇到的必须是花,那么我们直接输出 f[n][m][0]f[n][m][0]f[n][m][0] 肯定是错误的答案。 因为这并不能保证最后一次遇到的是花,因为最后是0壶酒,那么在遇到最后一朵花时应该还剩1壶酒,所以我们可以输出 f[n][m−1][1]f[n][m-1][1]f[n][m−1][1] 作为答案。

3.Ac_code

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 110;int n, m;
//已经遇到i次店,j次花,还剩k斗酒的方案数
LL f[N][N][N];
void solve()
{cin >> n >> m;f[0][0][2] = 1;for (int i = 0; i <= n; ++i) {for (int j = 0; j <= m; ++j) {for (int k = 0; k <= m; ++k) {//最后一次遇到店if (i && k % 2 == 0) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) % mod;//最后一次遇到花if (j) f[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) % mod;}}}cout << f[n][m - 1][1] << '\n';
}
int main()
{ios_base :: sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--){solve();}return 0;
}

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...