h*******8
发帖数: 29 | 1 搞了一个下午，一直超时，难道复杂度可以比O(n^2)小么。请教各位了。感觉自己实在
是太菜了。
代码是依据以下的方程，a[N]是input
f[i] = max( max(for all j, 0
(i-1)*a[i] - (a[1]+a[2]+...+a[i-1]) )
以下是代码
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
int N;
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
temp -= a[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<
else cout<
}
return 0;
} | m****1
发帖数: 41 | 2 这题我正好做过~
好像是O(nlogn)
idea 是这样，依据题意，假如第i天的股价最高，那么前 i-1天都是买， 第i天卖 赚
最多
好，处理完一次以后，前i个可以不看了，从i+1开始，再找从i+1到结尾 最大的最大股
价，重复操作直到 i = size of array -1;
建一个
struct day {
int value; //当天的股价
int id; // 第id天
}
对 value 进行 NlogN 的排序，
然后扫一遍 就Ok | m****1
发帖数: 41 | 3 部分程序
long long process (int * my,int start,int end,int curmax) {
long long sum = 0;
for(int i=start;i
sum += curmax - my[i];
return sum;
}
void solution ( int n) {
int a[n];
node mynode[n];
for(int i=0;i
cin >> a[i];
mynode[i].id = i;
mynode[i].value = a[i];
}
mergeSort(mynode,n);
int curmaxId = -1;
int curmax;
long long total = 0;
for(int i=0;i
int id = mynode[i].id;
curmax = mynode[i].value;
if(id > curmaxId){
total += process(a,curmaxId+1,mynode[i].id,curmax);
curmaxId = id;
}
}
cout<< total <
} | p*****2
发帖数: 21240 | | w***o
发帖数: 109 | | h*******8
发帖数: 29 | 6 多谢回复，不过诚如二爷所说，这题是greedy。
你的思路也是greedy。
放在dp底下的确有点误导，待会重写个。
【在 m****1 的大作中提到】
: 这题我正好做过~
: 好像是O(nlogn)
: idea 是这样，依据题意，假如第i天的股价最高，那么前 i-1天都是买， 第i天卖 赚
: 最多
: 好，处理完一次以后，前i个可以不看了，从i+1开始，再找从i+1到结尾 最大的最大股
: 价，重复操作直到 i = size of array -1;
: 建一个
: struct day {
: int value; //当天的股价
: int id; // 第id天
| m****1
发帖数: 41 | | r**h
发帖数: 1288 | 8 这题的思路和只能买卖一次求最大利润那一题完全一样
只是题目介绍容易把人唬住了 |
|
|
