题解 - Vijos

2

xitele LV 7 @ 2017-03-25 10:30:11

#include <iostream>
#include <memory.h>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <set>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
long long i,a[100005],n,ans;
int main()
{
while(cin>>n)
{
ans=0;
for(i=0;i<n;i++) cin>>a[i];
for(i=1;i<n-1;i++)
{
if(a[i]>a[i-1]&&a[i]>a[i+1])
{
ans=ans+min(abs(a[i+1]-a[i]),abs(a[i-1]-a[i]));
a[i]=max(a[i-1],a[i+1]);
}
else if(a[i]<a[i-1]&&a[i]<a[i+1])
{
ans=ans+min(abs(a[i+1]-a[i]),abs(a[i-1]-a[i]));
a[i]=min(a[i-1],a[i+1]);
}
}
for(i=1;i<n;i++) ans=ans+abs(a[i]-a[i-1]);
cout<<ans<<endl;
}
system("pause");
return 0;
}

2

xitele LV 7 @ 2017-03-25 10:26:27

#include <iostream>
#include <memory.h>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <set>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
long long i,a[100005],n,ans;
int main()
{
while(cin>>n)
{
ans=0;
for(i=0;i<n;i++) cin>>a[i];
for(i=1;i<n-1;i++)
{
if(a[i]>a[i-1]&&a[i]>a[i+1])
{
ans=ans+min(abs(a[i+1]-a[i]),abs(a[i-1]-a[i]));
a[i]=max(a[i-1],a[i+1]);
}
else if(a[i]<a[i-1]&&a[i]<a[i+1])
{
ans=ans+min(abs(a[i+1]-a[i]),abs(a[i-1]-a[i]));
a[i]=min(a[i-1],a[i+1]);
}
}
for(i=1;i<n;i++) ans=ans+abs(a[i]-a[i-1]);
cout<<ans<<endl;
}
system("pause");
return 0;
}

0

Vijos永远NB (郑灏轩) LV 10 @ 2021-12-19 16:55:57

做题超500咯~~

0

nzhtl1477 LV 10 @ 2014-11-05 01:10:30

P1615旅行
Accepted

记录信息

评测状态 Accepted
题目 P1615 旅行
递交时间 2014-11-05 01:09:27
代码语言 C++
评测机 VijosEx
消耗时间 193 ms
消耗内存 672 KiB
评测时间 2014-11-05 01:09:29

评测结果

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 668 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 668 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 668 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 672 KiB, score = 10

测试数据 #4: Accepted, time = 31 ms, mem = 672 KiB, score = 10

测试数据 #5: Accepted, time = 23 ms, mem = 668 KiB, score = 10

测试数据 #6: Accepted, time = 31 ms, mem = 672 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 672 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 672 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 672 KiB, score = 10

Accepted, time = 193 ms, mem = 672 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>

using namespace std;

int a[100000 + 2];
int n;
int i;
unsigned long long ans;

int abs( int a )
{
if( a > 0 )
return a;
return -a;
}

int main()
{
while( scanf( "%d" , &n ) != EOF )
{
ans = 0;
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &a[i] );
for( i = 2 ; i < n ; i++ )
if( a[i - 2] < a[i - 1] && a[i - 1] > a[i] )
{
ans += a[i - 1] - max( a[i - 2] , a[i] );
a[i - 1] = max( a[i - 2] , a[i] );
}
else if( a[i - 2] > a[i - 1] && a[i - 1] < a[i] )
{
ans += min( a[i - 2] , a[i] ) - a[i - 1];
a[i - 1] = min( a[i - 2] , a[i] );
}
for( i = 1 ; i < n ; i++ )
ans += abs( a[i] - a[i - 1] );
cout << ans << endl;
}
return 0;
}

weak!

0

xiewenzhao LV 8 @ 2014-11-03 23:20:20

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 952 KiB, score = 10

测试数据 #1: Accepted, time = 7 ms, mem = 952 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 948 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 952 KiB, score = 10

测试数据 #4: Accepted, time = 328 ms, mem = 948 KiB, score = 10

测试数据 #5: Accepted, time = 328 ms, mem = 952 KiB, score = 10

测试数据 #6: Accepted, time = 343 ms, mem = 944 KiB, score = 10

测试数据 #7: Accepted, time = 328 ms, mem = 948 KiB, score = 10

测试数据 #8: Accepted, time = 343 ms, mem = 952 KiB, score = 10

测试数据 #9: Accepted, time = 328 ms, mem = 948 KiB, score = 10

Accepted, time = 2035 ms, mem = 952 KiB, score = 100

代码

#include<iostream>
#include<cmath>
using namespace std;
int a[100000];
long long ans=0;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++)
{
if(a[i]>a[i-1] && a[i]>a[i+1])
{
ans+=a[i]-max(a[i-1],a[i+1]);
a[i]=max(a[i-1],a[i+1]);
}
if(a[i]<a[i-1] && a[i]<a[i+1])
{
ans+=min(a[i-1],a[i+1])-a[i];
a[i]=min(a[i-1],a[i+1]);
}
ans+=abs(a[i-1]-a[i]);
}
cout<<ans;
return 0;
}

vijos复活后第一题

0

panyue LV 9 @ 2013-07-15 13:37:15

var
n,i,p,q:longint;
a:array[0..100001] of longint;
ans:qword;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
for i:=2 to n do
begin
p:=a[i-1] ; q:=a[i+1];
if ((p>a[i]) and (a[i]>q)) or ((p<a[i]) and (a[i]<q)) then begin ans:=ans+abs(a[i]-p); continue end;
if (a[i]<=p) and (a[i]<=q) then begin ans:=ans+min(p,q)-a[i]; a[i]:=min(p,q); ans:=ans+abs(a[i]-p); continue end;
if (a[i]>=p) and (a[i]>=q) then begin ans:=ans+a[i]-max(p,q); a[i]:=max(p,q); ans:=ans+abs(a[i]-p); continue end;
end;
writeln(ans);
end.

0

843279365 LV 8 @ 2012-07-29 15:18:43

不知道怎么证明，稀里糊涂就过了。

0

勇敢汉堡包 LV 8 @ 2010-04-15 11:29:49

"显然对于所有情况，都有如果a[i]修改过，那么a就不会再改或者改成和a[i]一样的数值，" 这对吗。。楼下好多大牛都这样说啊

反例

105 100 110 108

0

fenghao LV 10 @ 2009-11-09 08:36:04

由传递性简单易证，当a[i]为valley或peak时变为周围的min或max最优。。

0

arstonliu LV 6 @ 2009-10-22 21:06:11

0

不会写题目 LV 8 @ 2009-10-09 08:55:28

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：运行超时|无输出...

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

为什么!!~- -

0

llzzpp999 LV 8 @ 2009-10-07 15:32:01

乱搞秒杀………………

0

qqtababa LV 6 @ 2009-10-04 09:54:25

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

哈哈哈哈

0

pascalcoco LV 8 @ 2009-10-02 20:36:04

如何证明贪心可以得到最优解?

0

gsrq LV 10 @ 2009-09-23 21:41:31

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var i,n:longint;

a:array[0..100005]of longint;

x:int64;

function max(x,y:longint):longint;

begin

if x>y then max:=x else max:=y;

end;

function min(x,y:longint):longint;

begin

if xa)and(a[i]>a) then

begin

x:=x+abs(a[i]-max(a,a));

a[i]:=max(a,a);

end;

if (a[i]

0

zhangk LV 10 @ 2009-09-06 14:42:06

这题也可以快排，再算sum=sum+abs(a[i]-a)(1

0

11022908 LV 9 @ 2009-09-04 11:10:15

假设存在 a[i]

a[i]是低谷（a[i]a)。

这样就把a[i]调节成与它最接近的旁边两个之中的一个数。

！！这样确定了局部从a经过a[i]走到a不会走重复的高度了！！

显然对于所有情况，都有如果a[i]修改过，那么a就不会再改或者改成和a[i]一样的数值，据此必然有无论a如何变化从a[i] 到a的路程总值都不变。

从这里在把a当成a[i]处理，这样每次每次处理出来的都是局部最优最优的解。根据a[i] 到a的路程总值都不变就从局部推广到了整体，因此只要不断重复处理，最终结果必然是最优!

0

淘淘 LV 8 @ 2009-08-21 17:44:00

证法1：对于a,b,c,d 当b在[a,c]中，最优；

对于b,c,d 使c在中，最优；并且使c在中的同时不违反b在[a,c]中，所以全局最优

证法2：对于一个序列满足任意a[i]在【a,a】之间必有c在中，如果使c在外，必然更劣，所以这样最优，所以生成这样的序列

这样证对吗？

0

lishunzhi LV 9 @ 2009-08-21 10:01:39

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var i,n:longint;

a:array[0..100005]of longint;

x:int64;

function max(x,y:longint):longint;

begin

if x>y then max:=x else max:=y;

end;

function min(x,y:longint):longint;

begin

if xa)and(a[i]>a) then

begin

x:=x+abs(a[i]-max(a,a));

a[i]:=max(a,a);

end;

if (a[i]

0

z2309323 LV 7 @ 2009-08-19 09:46:18

f表第i个调整为高度j的最优值。k枚举第i-1个的高度。

F=Min{F+(H[i]-J)+|j-k|}

o(n^3),dp它干嘛？

但这位同学问dp算法的这种精神还是值得学习的。

因为如果把调整第m个的高度和从m走到m+1的代价都改变一下，不是系数为1这样的代价的话，贪心显然就不可以了。

我做过的原题是(姜碧野出的，为避嫌说明一下)，

从m走到m+1的代价=c*高度差，调整第m个的高度的代价是(j-h[m])^2。对于这道题来讲，只能用dp了。

F=Min{F+(Hi-J)^2+C*|j-k|}

对此方程的优化我就先不写了。

题解

50 条题解

旅行

信息

状态

开发

支持

题解

50 条题解

旅行

信息

状态

开发

支持

还没有账户？

登录