链家编程第一题,有木有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;
}
全部评论
他给的是三维坐标,我给铺开了,变成二维的,三维的不好找转移方程,寻找前置状态比较麻烦 #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
题目都没有?
点赞 回复 分享
发布于 2017-09-03 12:53

相关推荐

斑驳不同:还为啥暴躁 假的不骂你骂谁啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务