「BZOJ1345」[Baltic2007] 序列问题Sequence
Description
对于一个给定的序列a1, …, an，我们对它进行一个操作reduce(i)，该操作将数列中的元素ai和ai+1用一个元素max(ai，ai+1)替代，这样得到一个比原来序列短的新序列。这一操作的代价是max(ai，ai+1)。进行n-1次该操作后，可以得到一个长度为1的序列。我们的任务是计算代价最小的reduce操作步骤，将给定的序列变成长度为1的序列。
Input
第一行为一个整数n( 1 <= n <= 1,000,000 )，表示给定序列的长度。接下来的n行，每行一个整数ai（0 <=ai<= 1, 000, 000, 000），为序列中的元素。
Output
只有一行，为一个整数，即将序列变成一个元素的最小代价。
Sample Input
3
1
2
3
1
2
3
Sample Output
5
题解
维护单调递减栈
栈中是4 3 2 1，合并代价至少是4+3+2
加入元素可以这样考虑
栈中有3 1，要加入4，之后要将1合并掉，则代价最小是3
要加入2，之后要将1合并掉，则代价最小是2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include<iostream> #include<cstdio> #define inf 0x7fffffff using namespace std; int n,top,s[1000001]; long long ans; int main() { scanf("%d",&n); s[0]=inf; for(int i=1;i<=n;i++) { int x;scanf("%d",&x); while(top&&x>=s[top]) { if(x>=s[top-1]) {ans+=s[top-1];top--;} else {ans+=x;top--;} } s[++top]=x; } while(top>1) ans+=s[--top]; printf("%lld",ans); return 0; } |
计数器 9786095
OI 课件=>
OI 课件=>
#include <cstdio>
);
>A[i-1]) res+=A 
;
>=A[i+1]) res+=A 
;
using namespace std;
int A[1000010];
int main()
{
int n;
long long res=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&A
A[0]=A[n+1]=2147483645;
for(int i=1;i<=n;i++)
{
if(A
if(A
}
printf("%lldn",res);
return 0;
}
这道题不是有非常直观的做法吗。。
好吧是我蒟蒻