头像

sysml


访客:5402

离线:4个月前



sysml
2019-05-27 15:21
int main(){
    int N,V;
    cin>>N>>V;
    vector<int> weight(N+1),value(N+1);
    for(int i=1;i<=N;i++)
        cin>>weight[i]>>value[i];
    reverse(weight.begin()+1,weight.end());
    reverse(value.begin()+1,value.end());
    vector<vector<int>> dp(N+1,vector<int>(V+1,0)); 
    for(int i=1;i<weight.size();i++){
        for(int j=0;j<=V;j++){

            if(j-weight[i]<0) 
                dp[i][j]=dp[i-1][j];

            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
        }
    }

    for(int i=weight.size()-1;i>=1;i--){
        if(V-weight[i]>=0 && dp[i][V]==dp[i-1][V-weight[i]]+value[i]){ 
            cout<<weight.size()-i<<" ";
            V-=weight[i];
        }

    }

    cout<<endl;
}



sysml
2019-05-24 03:37
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,V;
    cin>>N>>V;
    vector<int> weight(N),value(N);
    for(int i=0;i<N;i++)
        cin>>weight[i]>>value[i];
    vector<int> f(V+1,0);
    for(int i=0;i<weight.size();i++){
        for(int v=weight[i];v<=V;v++){
            f[v]=max(f[v],f[v-weight[i]]+value[i]);
        }
    }
    cout<<f[V]<<endl;
}

int main(){
    int N,V;
    cin>>N>>V;
    vector<int> weight(N+1),value(N+1);
    for(int i=1;i<=N;i++)
        cin>>weight[i]>>value[i];
    vector<vector<int>> dp(N+1,vector<int>(V+1,0)); 
    for(int i=1;i<weight.size();i++){
        for(int j=0;j<=V;j++){
            for(int k=0;k*weight[i]<=j;k++){
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*weight[i]]+k*value[i]);    
            }
        }
    }
    cout<<dp[N][V]<<endl;
}


int main(){
    int N,V;
    cin>>N>>V;
    vector<int> weight(N+1),value(N+1);
    for(int i=1;i<=N;i++)
        cin>>weight[i]>>value[i];
    vector<vector<int>> dp(N+1,vector<int>(V+1,0)); 
    for(int i=1;i<weight.size();i++){
        for(int j=0;j<=V;j++){

            dp[i][j]=dp[i-1][j];

            if(j-weight[i]>=0) 
                dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
        }
    }
    cout<<dp[N][V]<<endl;
}




sysml
2019-05-20 03:09
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p || root==q) return root;
        if(root==nullptr) return nullptr;
        auto l=lowestCommonAncestor(root->left,p,q);
        auto r=lowestCommonAncestor(root->right,p,q);
        if(l && r) return root;
        if(l) return l;
        return r;
    }
};



sysml
2019-05-20 03:08
class Solution {
public:
    int strToInt(string str) {
        long long res=0;
        int i=0;
        while(i<(int)str.size() && str[i]==' ') i++;
        int flag=1;
        if(str[i]=='-'){
            flag=-1;
            i++;
        }
        else if(str[i]=='+'){
            i++;
        }
        while(i<(int)str.size()){
            if(str[i]<'0' || str[i]>'9') break;
            res*=10;
            res+=(str[i]-'0');
            i++;
            if(res>INT_MAX) return flag==1?INT_MAX:INT_MIN;
        }
        return flag*res;
    }
};


活动打卡代码 AcWing 86. 构建乘积数组

sysml
2019-05-20 03:08
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res(A.size(),1);
        if(A.size()==0) return res;
        int t=A[0];
        for(int i=1;i<A.size();i++){
            res[i]*=t;
            t*=A[i];
        }

        t=A.back();
        for(int j=A.size()-2;j>=0;j--){
            res[j]*=t;
            t*=A[j];
        }
        return res;
    }
};



sysml
2019-05-20 03:08
class Solution {
public:
    int add(int num1, int num2){
        if(!num1) return num2;
        if(!num2) return num1;
        return add((num1&num2)<<1,(num1^num2)); // 第一个参数是进位,第二个参数是不进位的加法
    }
};


活动打卡代码 AcWing 84. 求1+2+…+n

sysml
2019-05-20 03:07
class Solution {
public:
// yxc的做法,和剑指offer的解法二一个意思
    int getSum(int n) {
        int res=n;
        n>0 && (res+=getSum(n-1));// 等价于:if(n>0) res+=getSum(n-1);
        return res;
    }

};



sysml
2019-05-20 03:07
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int res=INT_MIN;
        int mv=INT_MAX;
        for(int i=0;i<nums.size();i++){
            mv=min(mv,nums[i]);
            res=max(res,nums[i]-mv);
        }
        return res;
    }
};



sysml
2019-05-20 03:07
class Solution {
public:
    // 剑指offer的解法,数学
    // yxc讲得更好:新编号到旧编号的映射
    int lastRemaining(int n, int m){
        if (n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }

    // 自己模拟的解法,暴力简单
    int lastRemaining1(int n, int m){
        vector<int> vec(n);
        for(int i=0;i<n;i++) vec[i]=1;
        bool flag=true;
        int sum=n;
        int count=0;
        int i=0;
        while(sum!=1){
            if(vec[i]==1){
                count++;
                if(count==m){
                    // cout<<i<<endl;
                    vec[i]=0;
                    count=0;
                    // i=0; // 题目有歧义:看来是删完之后继续数,而不是从头数。
                    sum--;
                    flag=false;
                }
            }
            if(flag){
                i=(i+1)%n;
            }
            flag=true;

        }
        for(int i=0;i<vec.size();i++){
            if(vec[i]) return i;
        }
        return INT_MAX;

    }
};


活动打卡代码 AcWing 81. 扑克牌的顺子

sysml
2019-05-20 03:06
class Solution {
public:
    bool isContinuous( vector<int> numbers ) {
        if(numbers.size()!=5) return false;
        sort(numbers.begin(),numbers.end());
        for(int i=1;i<numbers.size();i++)
            if(numbers[i]!=0 && numbers[i]==numbers[i-1]) return false;
        int i=0;
        while(i<numbers.size() && numbers[i]==0) i++;
        int l=numbers[i];
        int r=numbers.back();
        if(l+5-1!=r) return false;
        // int d=numbers.size()-1-i+1;
        // return d+i==5;
        return true;

    }
};