阿里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;
}