阿里2020-07-17提前批二道AC代码(二)。

题目忘了。
后面看有没有人记得,补。


#include <bits/stdc++.h>
#include "iostream"
using namespace std;
const int N = 1010;
int n, m, c0, d0;
int a, b, c, d;

struct Node {
    int v, w;
};

int dp[1010][1010];
//int dp[N];
int main() {

    vector<Node> ns;
    cin>>n>>m>>c0>>d0;
    for (int i = 0; i < m; ++i) {
        cin>>a>>b>>c>>d;
        int cnt = a / b, k = 1;
        //问题转化为01背包
        //多重背包转化01背包第二层次优化做法(第一层次 不优化,遍历全部k,第二层次,通过1 2 4 8这种因式分解,第三层次 单调队列)
        //任何正整数数都可以 通过 1 2 4 8 等加上余数 表示。优化解空间。
        while (cnt) {
            if (cnt >= k) {
                ns.push_back(Node{k * c, k * d});
                cnt -= k;
                k *= 2;
            } else {
                ns.push_back(Node{cnt * c, cnt * d});
                cnt = 0;
            }
        }
    }
//    for (int i = 0; i < ns.size() + 1; ++i) {
//        if (i == ns.size()) {
//            for (int j = c0; j <= n; ++j)
//                dp[j] = max(dp[j], dp[j - c0] + d0);
//        } else {
//            for (int j = n; j >= ns[i].v; --j)
//                dp[j] = max(dp[j], dp[j - ns[i].v] + ns[i].w);
//        }
//    }
//    printf("%d\n", dp[n]);
//
   //填充 0,0  做为01背包初始化
    ns.insert(ns.begin(),{0,0});
    for(int i = 1;i<ns.size()+1;i++){
        //遍历全部ns中结点,属于01背包问题
        if(i!=ns.size()){
            for(int j = 0;j<=n;j++){
                if(j<ns[i].v){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-ns[i].v]+ns[i].w);
                }
            }
        } else{
            //当ns中结点都遍历完了,开始通过剩余物品的更新dp,此时转化为完全背包(只要体积够,可无限使用)。
            for(int j = 0 ; j<=n ;j++){
                dp[i][j] = dp[i-1][j];
                if(c0<=j){
                    dp[i][j]=max(dp[i][j],dp[i][j-c0]+d0);
                }
            }
        }
    }
    cout<<dp[ns.size()][n];
    return 0;
}

#阿里巴巴#
全部评论
是正式批吧,不是提前批
1 回复 分享
发布于 2020-07-21 09:34

相关推荐

伟大的烤冷面被普调:暨大✌🏻就是强
点赞 评论 收藏
分享
评论
点赞
4
分享
牛客网
牛客企业服务