Luogu 1164 小A点菜

电玩女神 2021-12-10 05:47 206阅读 0赞

终于在任重而道不远的形势的逼迫下，拾起了自己畏惧的动态规划。

于是开始从最简单的题做起。

题目链接：[https://www.luogu.org/problemnew/show/P1164][https_www.luogu.org_problemnew_show_P1164]

思路：

第一眼，搜索。

第二眼，奇怪的dp。

第三眼，完全背包。

搜索（较容易实现）：

#include <bits/stdc++.h>
    const int MAXN=100050;
    using namespace std;
    int n,m,ans,a[MAXN];
    bool vis[MAXN];
    void dfs(int x,int y){
        if(y==0){
            ans++;
            return ;
        }
        for(int i=x+1;i<=n;i++){
            if(!vis[i]&&y>=a[i]){
                vis[i]=true;
                dfs(i,y-a[i]);
                vis[i]=false;
            }
        }
    }
    int main(){
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        dfs(0,m);
        printf("%d\n",ans);
        return 0;
    }

奇怪的dp（非正确做法）：

自己想的一种"dp"做法。

设$f\[x\]$表示能表示出$x$的所有方案数，然后用乘法原理搞一下。

主体部分：

for(int i=1;i<=n;i++) cin>>a[i],f[a[i]]++,Max=max(Max,f[a[i]]);
        //init();
        for(int i=1;i<=m;i++){
            for(int j=1,l=i-1;j<=l;j++,l--){
                if(j!=l) f[i]+=f[j]*f[l];
                else f[i]+=b[i-1];
            }
        }

其中$b\[i\]$表示$i-1$的阶乘值，这个显然能推出来。

但是具有后效性，故是一个完全错误的想法。

完全背包：

updating...

转载于:https://www.cnblogs.com/BeyondLimits/p/11130035.html

[https_www.luogu.org_problemnew_show_P1164]: https://www.luogu.org/problemnew/show/P1164

发表评论取消回复

表情：

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

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

相关阅读

相关 P1164 小A点菜（洛谷训练场）题解

文章目录题目描述输入格式输出格式输入输出算法分析解题标程（二维dp）算法优化

水深无声/ 2022年12月28日 07:26/ 0 赞/ 132 阅读

相关【基础练习】【背包DP】洛谷1164 小A点菜题解

洛谷的题目又有那令人···的悲剧格式= = 洛谷1164 小A点菜本题地址：[ http://www.luogu.org/problem/show?pid=1164]

矫情吗；*/ 2022年08月03日 13:50/ 0 赞/ 164 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 319 阅读

相关洛谷P1164 小A点菜

题目背景 uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。 uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。题

曾经终败给现在/ 2022年05月28日 07:10/ 0 赞/ 179 阅读

相关动态规划之小A点菜

题目背景 `uim`神犇拿到了`uoi`的`ra`（镭牌）后，立刻拉着基友`小A`到了一家……餐馆，很低端的那种。 `uim`指着墙上的价目表（太低级了没有菜单），说：

我会带着你远行/ 2022年05月04日 11:00/ 0 赞/ 194 阅读

相关 P1164 小A点菜

题目描述：不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩MMM元(M≤10000)(M \\le 10000)(M≤10000)。餐馆虽低端，但是菜品种类不

忘是亡心i/ 2022年02月28日 04:16/ 0 赞/ 166 阅读

相关 Luogu1993小K的农场

include<cstdio> include<queue> include<cstring> using namespace std;

r囧r小猫/ 2021年12月24日 19:17/ 0 赞/ 219 阅读

相关 [FFT]luogu P1919 A*B Problem升级版

https://www.luogu.org/problemnew/show/P1919 分析可以把一个数化为多项式的系数，如233 3+3x+2x^2 然后便可以

àì夳堔傛蜴生んèń/ 2021年12月16日 01:09/ 0 赞/ 153 阅读

相关 Luogu 1164 小A点菜

终于在任重而道不远的形势的逼迫下，拾起了自己畏惧的动态规划。于是开始从最简单的题做起。题目链接：[https://www.luogu.org/problemnew/sh

电玩女神/ 2021年12月10日 05:47/ 0 赞/ 207 阅读

相关 Java后台——点餐小程序点餐系统菜品管理

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

比眉伴天荒/ 2021年07月25日 11:46/ 0 赞/ 424 阅读