黑客rank Stock Maximize# JobHunting - 待字闺中
h*8
1 楼
搞了一个下午，一直超时，难道复杂度可以比O(n^2)小么。请教各位了。感觉自己实在
是太菜了。
代码是依据以下的方程，a[N]是input
f[i] = max( max(for all j, 0
以下是代码
int main() {
int T;
#define RF
#ifdef RF
ifstream& in = ifstream("input.txt" , ios::in);
#else
istream& in = cin;
#endif
in>>T;
for(int t=0 ; t
in>>N;
vector a(1,0);
vector cache(1 , 0);
int accu = 0;
for(int k=1 ; k<=N ; ++k) {
int t;
in>>t;
a.push_back(t);
accu += t;
cache.push_back(accu);
}
vector f(N+1 , 0);
f[1] = a[1]*(-1);
for(int i=2 ; i<=N ; i++){
int maxval = f[1];
int temp = cache[i-1]-a[1];
for(int j = 2 ; j
maxval = max(maxval , f[j] + (i-1-j)*a[i] - temp);
}
maxval = max(maxval , (i-1)*a[i] - cache[i-1]);
f[i] = maxval;
}
if(f[N]<0) cout<<0<
return 0;
}
是太菜了。
代码是依据以下的方程，a[N]是input
f[i] = max( max(for all j, 0
以下是代码
int main() {
int T;
#define RF
#ifdef RF
ifstream& in = ifstream("input.txt" , ios::in);
#else
istream& in = cin;
#endif
in>>T;
for(int t=0 ; t
in>>N;
vector
vector
int accu = 0;
for(int k=1 ; k<=N ; ++k) {
int t;
in>>t;
a.push_back(t);
accu += t;
cache.push_back(accu);
}
vector
f[1] = a[1]*(-1);
for(int i=2 ; i<=N ; i++){
int maxval = f[1];
int temp = cache[i-1]-a[1];
for(int j = 2 ; j
maxval = max(maxval , f[j] + (i-1-j)*a[i] - temp);
}
maxval = max(maxval , (i-1)*a[i] - cache[i-1]);
f[i] = maxval;
}
if(f[N]<0) cout<<0<
return 0;
}
