啊这,为什么用了常数优化反而tle了
查看原帖
啊这,为什么用了常数优化反而tle了
323744
littlecyber楼主2020/7/25 23:53

倒数第二个tle了,有大佬帮看看嘛

#include <bits/stdc++.h>
#define maxn 5000+10
#define maxm 50000+10
#define memset(a,b) memset(a,b,sizeof(a))
using namespace std;
//这里价值就是重量
int vt[maxn],dp[maxm],accu[maxn];
int main()
{
    int c,h;
    cin>>c>>h;
    memset(dp,0);
    cin>>vt[0];accu[0]=vt[0];
    for(int i=1;i<h;i++){cin>>vt[i];accu[i]=accu[i-1]+vt[i];}
    for(int i=0;i<h;i++)
        for(int j=c;j>=max(vt[i],c-accu[h-1]+accu[i]);j--)dp[j]=max(dp[j],dp[j-vt[i]]+vt[i]);
    cout<<dp[c];
    return 0;
}

2020/7/25 23:53
加载中...