本文主要是介绍第 2 届河北省大学生程序设计竞赛(河北省赛)-Problem J. icebound 的商店-题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
传送门
Problem A. Mex Query
Problem B. Nim Game
Problem C. icebound 的账单
Problem G. 520
Problem H. 神殿
Problem J. icebound 的商店
Problem K. Bitmap
哈希讲解
二维哈希讲解
Problem L. 跑图
文章目录
- 传送门
- Problem A. Mex Query
- Problem B. Nim Game
- Problem C. icebound 的账单
- Problem G. 520
- Problem H. 神殿
- Problem J. icebound 的商店
- Problem K. Bitmap
- Problem L. 跑图
- Problem J. icebound 的商店
Problem J. icebound 的商店
Time Limit: 1000ms
Memory Limit: 65536KB
Description
icebound在得到神殿的宝藏之后,开了一家神秘的商店。你来到了商店,发现慷慨的icebound搞了 T T T次促销活动。在每次促销活动中,icebound都会想出一个他喜欢的数字,如果你买的商品的总价刚好等于icebound喜欢的数字,那么你就可以免费得到这些商品。
icebound的商店里一共有 15 15 15 件商品,商品的价格和这家商店一样神秘,第一件商品的价格是 1 1 1 元,第二件商品的价格是 2 2 2 元,设第 n n n件商品的价格为 w n w_n wn元,则:
w n = w n − 1 + w n − 2 ( 3 ≤ n ≤ 15 ) w_n = w_{n-1} + w_{n-2} (3 \leq n \leq 15) wn=wn−1+wn−2(3≤n≤15)
如果在某次活动中icebound喜欢的数字是 4 4 4,那么共有 4 4 4 种购买方案:
- 买 4个 第一种商品
- 买 2个 第一种商品 和 1个 第二种商品
- 买 2个 第二种商品
- 买 1个 第一种商品 和 1个 第三种商品
请你算出共有多少种方案可以免费购物,方案数对 1000000009 ( = 1 0 9 + 9 ) 1000000009(=10^9+9) 1000000009(=109+9)取模。
Input
第一行给出一个整数 T T T,表示icebound搞了 T T T次活动。
接下来的 T T T行每行给出一个正整数 x x x,表示在这次活动中icebound喜欢的数字。
1 ≤ T ≤ 3000 1 \leq T \leq 3000 1≤T≤3000
1 ≤ x ≤ 3000 1 \leq x \leq 3000 1≤x≤3000
Output
输出 T T T行,每行输出一个正整数。
第 i i i行的正整数表示在第ii次活动中免费购物的方案数,方案数对 1000000009 ( = 1 0 9 + 9 ) 1000000009(=10^9+9) 1000000009(=109+9)取模。
Sample Input
3
5
20
30
Sample Output
6
134
509
题目大意
icebound的商店共有 15 15 15种商品,每种商品有无限多个。
其中前两件商品的价格分别是 1 1 1和 2 2 2,从第 3 3 3件商品开始,每件商品的价格为前两件商品的和。
每次给你一个数 n n n,问你有多少种选法,使得商品总价格为 n n n。
解题思路
这是一道完全背包题。简单说一下:
我们可以用 d p [ j ] dp[j] dp[j]来表示总价为 j j j的选择方案。那么在选择第 i i i件商品时,我们有: d p [ j ] = d p [ j ] + d p [ j − f b n q [ i ] ] dp[j]=dp[j]+dp[j-fbnq[i]] dp[j]=dp[j]+dp[j−fbnq[i]](其中 f b n q [ i ] fbnq[i] fbnq[i]代表第 i i i件商品的价格)。
即:如果不选这第 i i i件商品,方案数还是原来的方案数 d p [ j ] dp[j] dp[j];如果选择这第 i i i件商品,方案数就是价格为 j − 第 i 件 商 品 的 价 格 j-第i件商品的价格 j−第i件商品的价格的方案数,即 d p [ j − f b n q [ i ] ] dp[j-fbnq[i]] dp[j−fbnq[i]]。
初始值 d p [ 0 ] = 1 dp[0]=1 dp[0]=1,购买总价为 0 0 0的商品的方案只有一种:啥都不买。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int dp[3010]={0};
ll fbnq[16];
ll mod=1000000009;
int main()
{fbnq[1]=1,fbnq[2]=2;for(int i=3;i<=15;i++)fbnq[i]=fbnq[i-1]+fbnq[i-2];dp[0]=1;for(int i=1;i<=15;i++)for(int j=fbnq[i];j<=3005;j++)dp[j]+=dp[j-fbnq[i]],dp[j]%=mod;int n;cin>>n;while(n--){int t;cin>>t;cout<<dp[t]<<endl;}return 0;
}
原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/116536351
这篇关于第 2 届河北省大学生程序设计竞赛(河北省赛)-Problem J. icebound 的商店-题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!