链家编程第一题,有木有dalao帮忙看看为啥通过率一直73%

#include<vector>
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int n,v;
    scanf("%d%d",&n,&v)
    vector<vector<int>> dp(2,vector<int>(v+1,0));
    vector<int> m(n),w(n),s(n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&m[i],&w[i],&s[i]);
    }
    for(int j=0;j<=v;j++)
    {
            if(j/w[0]<=m[0])
           {
               dp[0][j]=j/w[0]*s[0];
           }
           else
           {
               dp[0][j]=m[0]*s[0];
           }
    }
    int f=1;
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<=v;j++)
        {
            dp[f][j]=dp[1-f][j];
            for(int z=1;z<=m[i];z++)
            {
                if(j-z*w[i]>=0)
                {
                    dp[f][j]=max(dp[1-f][j],dp[1-f][j-z*w[i]]+z*s[i]);
                }
                else
                {
                    break;
                }

            }
        }
        f=1-f;
    }
    cout<<dp[1-f][v]<<endl;    
    return 0;
}
全部评论
题目都没有?
点赞 回复 分享
发布于 2017-09-03 12:53
他给的是三维坐标,我给铺开了,变成二维的,三维的不好找转移方程,寻找前置状态比较麻烦 #include <bits/stdc++.h> #define ll long long #define ull unsigned long long using namespace std; struct thing { int w,s; }; thing things[20001]; int n,m,v,c=0,maxs=0,t[501]; int main(int argc, const char * argv[]) { memset(t,0,sizeof t); cin>>n>>v; for(int i=1,j=1;i<=n;++i) { scanf("%d%d%d",&m,&things[j].w,&things[j].s); c+=m; int k=1; for(;k<m;++k) { things[k+j].w=things[j].w,things[k+j].s=things[j].s; } j+=k; } for(int j=1;j<=c;++j) { for(int i=v;i>0;--i) { int k=i-things[j].w; t[i]=(k>=0?max(t[k]+things[j].s,t[i-1]):t[i-1]); maxs=max(maxs,t[i]); } } cout<<maxs; }
点赞 回复 分享
发布于 2017-09-02 21:53

相关推荐

10-02 19:29
已编辑
浙江科技大学 运营
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
正在热议
更多
# 你的mentor是什么样的人? #
3795次浏览 27人参与
# 你觉得mentor喜欢什么样的实习生 #
10187次浏览 283人参与
# 平安产险科技校招 #
2400次浏览 0人参与
# 帮我看看,领导说这话什么意思? #
6032次浏览 25人参与
# 没有家庭托举的我是怎么找工作的 #
12230次浏览 156人参与
# 怎么给家人解释你的工作? #
1337次浏览 16人参与
# 未岚大陆求职进展汇总 #
23803次浏览 111人参与
# 求职低谷期你是怎么度过的 #
5169次浏览 91人参与
# 26届秋招公司红黑榜 #
11674次浏览 40人参与
# 从哪些方向判断这个offer值不值得去? #
6497次浏览 91人参与
# 同bg的你秋招战况如何? #
158806次浏览 927人参与
# 度小满求职进展汇总 #
10058次浏览 49人参与
# 实习必须要去大厂吗? #
146606次浏览 1541人参与
# 校招泡的最久的公司是哪家? #
4482次浏览 22人参与
# 你有哪些缓解焦虑的方法? #
37172次浏览 835人参与
# 面试紧张时你会有什么表现? #
1687次浏览 20人参与
# 你喜欢工作还是上学 #
77566次浏览 860人参与
# 入职第一天,你准备什么时候下班 #
85471次浏览 467人参与
# 秋招想进国企该如何准备 #
97703次浏览 487人参与
# 简历无回复,你会继续海投还是优化再投? #
103577次浏览 819人参与
# 机械人的工作环境真的很差吗 #
24999次浏览 119人参与
# 独居后,你的生活是更好了还是更差了? #
28125次浏览 263人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务