【简单DP】牛客寒假集训营L 小沙の抱团 hard

￡神魔★判官ぃ 2024-03-27 11:36 70阅读 0赞

[L-小沙の抱团 hard\_2023牛客寒假算法基础集训营5 (nowcoder.com)][L-_ hard_2023_5 _nowcoder.com]

**虽然是一道简单DP，但是我连状态设计都想了好久，太久没写DP，已经形成思维定势了，得家训DP了**

题意：

![df482338d7f30ad09a410191dd638547.png][]

思路：

一开始想的状态是以第几个指令作为阶段的

但是显然这不是阶段，因为他可以无限次地做指令

所以这告诉了一个道理，不是所有的DP题的阶段都这么显然

这道题是以人数作为状态（人数决定了做那个指令决策），说把人数作为阶段，好像也比较勉强，然后DP值就是最小花费

没有特别明显的阶段的时候直接设状态

然后开始转移

转移的时候直接枚举先去状态，然后去枚举决策，可以求出去除模之后的最小花费

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=1e5+10,mxm=5e2+10;
    int n,m,sum=0;
    int v[mxn],x[mxn],dp[mxn];
    void solve(){
        memset(dp,0x3f,sizeof(dp));
        cin>>n>>m;
        for(int i=1;i<=m;i++) cin>>v[i]>>x[i];
        dp[n]=0;
        for(int i=n;i>2;i--){
            for(int j=1;j<=m;j++){
                int t=i/x[j]*x[j];
                dp[t]=min(dp[t],dp[i]+v[j]);
            }
        }
        for(int i=1;i<=n;i++){
            if(dp[i]<0x3f3f3f3f){
                cout<<dp[i]<<'\n';
                return;
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[L-_ hard_2023_5 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/46813/L
[df482338d7f30ad09a410191dd638547.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a5122a786cd5461c8a272c40bab554ac.png