333 条题解
-
0
laiming LV 4 @ 2013-06-20 13:28:38
为什么压72错2个，压100错3 个，压105 AC ？？？？？
-
0
-
玉术临风 @ 2013-03-16 17:06:58
无语……
-
ChinaLover @ 2013-08-24 17:25:58
没有！
-
华好少年 @ 2013-11-02 11:16:14
为何你到处乱发 为何你如此欠揍 为何你如此贱
-
cuichen @ 2014-09-08 20:34:21
骗访问量么？
-
基因库 @ 2014-10-23 22:31:26
傻么
-
东大微雕 @ 2015-02-01 21:11:41
混蛋，八嘎。
-
倾城依回释梦落红空巷琳影 @ 2016-04-17 19:53:36
2333333333333
-
jsezzxw @ 2017-07-22 19:12:55
混蛋，巴嘎
-
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
#include
using namespace std;
#include
int main()
{
long l,temp,k;
int s,t,m,i,j,min,sum;
long a[102],b[10000];
int f[10000];
cin>>l;
cin>>s>>t>>m;for(i=0;i>a[i];
if(s!=t)
{
for(i=0;i90)
{
k=a[0]-90;
for(j=0;j -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
var i,j,l,n,count,ans,s,t:longint;
a:array[0..100]of longint;
p:array[1..20000]of boolean;
f:array[0..20000]of longint;
procedure sort;
var i,j,temp:longint;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then
begin
temp:=a[i];a[i]:=a[j];a[j]:=temp;
end;
end;
procedure compress;
var i,j,len:longint;
begin
if s=t then
begin
for i:=1 to n do
if a[i] mod s=0 then inc(count);
writeln(count);
halt;
end;
sort;
len:=0;
fillchar(p,sizeof(p),false);
for i:=1 to n do
begin
if a[i]-len-a>s*t then len:=a[i]-(a+s*t);
dec(a[i],len);
p[a[i]]:=true;
end;
end;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
procedure dp;
var i,j:longint;
begin
filldword(f,sizeof(f)div 4,maxint);
f[0]:=0;
for i:=1 to a[n]+s*t do
for j:=i-s downto i-t do
if j>=0 then f[i]:=min(f[i],f[j])+ord(p[i]);
ans:=maxlongint;
for i:=a[n]+1 to a[n]+s*t do
if f[i] -
0
悲剧，我把两块石头的距离压在105之内了，但是100-110之间好像105能全部AC。
#include
using namespace std;int stone[101];
int n, s, t, m;
int f[20001];void
quickSort( int *arr, int head, int tail )
{
int h = head, t = tail;
int mid = arr[( h + t ) / 2];
while( h < t )
{
while( arr[h] < mid )
h++;
while( arr[t] > mid )
t--;
if( h > n >> s >> t >> m;
for( int i = 1; i > stone[i];
quickSort( stone, 1, m );
for( int i = 1; i 105 )
stone[i] = stone[i - 1] + ( stone[i] - stone[i - 1] ) % 105;
f[stone[i]] = 1;
}
n = stone[m] + t;
}void
_dp()
{
if( s == t )
{
for( int i = 1; i -
0
本题是一类很有意思的动态规划题；不同于决策优化，本题要求优化状态，这就使题目增加了很多的灵活性。
朴素的动态规划注意到当前状态只与其前面的T个状态有关；所以说采用滚筒法可以在O(LT)的时间内解决本题。但是，本题中L非常大，因此我们希望算法的时间复杂度与L无关。
一种想法是：将当前状态s与其前面的T个状态看作一个长度为T+1的状态数组，如果在一次滚筒更新中新旧两个数组完全一样，则在遇到下一块石头之前，状态将会完全不变。这个原则是很简单的，因为除非遇到一块石头，否则每一个决策的前提都是不变的，所以说滚筒更新下去，状态一定不变。
那么，我们就需要问一个问题：究竟会不会出现这种更新前后状态不变的情况呢？如果不会出现这些情况，那么算法的优化也就无从谈起了。事实上，只要S < T，就一定会出现这种情况。
这是很好理解的。假设S < T，则青蛙可以跳T步或T-1步，这两个步长是互质的。根据扩展的欧几里德定理，当路程足够长的时候，一定会出现这样一种情况：前后T步全部被同一个数覆盖；这就可以直接应用优化了。时间复杂度是O(NT)
当然，如果S = T，这个性质显然就不成立了，这种情况下我们可以特判。如果青蛙能够跳得步数不是连续的，这种优化还可以用吗？
可以的！如果青蛙跳得步数中有两个数是互质的，则优化立即生效；否则，我们将所有的石头的位置除以步数的最大公约数（不能被最大公约数整除的显然不可能被跳到），对总长度也做类似的变化，就可以套用优化方法了。
评价：这是NOIP中第一道DP优化题，虽然其难度远不如NOI，但其灵活度也不小，需要选手仔细地考察状态转移方程的特征，利用状态空间的稀疏性来进行优化。尤其是当S = T时这种特殊情况的讨论极易被选手遗漏。
AC……………………………………………………………………………………………………
program river;
const
maxn = 105;
maxk = 12;
infinity = 1000000000;
var
n : longint;
leng : longint;
stone : array[1..maxn] of longint;
minstep, maxstep : longint;
f, last : array[0..maxk] of longint;
ans : longint;function equal : boolean;
var
i : longint;
BEGIN
for i := 1 to maxstep do
if f[i] last[i] then exit(false);
exit(true);
END;procedure special_judge;
var
sum : longint;
i : longint;
BEGIN
sum := 0;
for i := 1 to n do
if stone[i] mod minstep = 0 then sum := sum + 1;
writeln(sum);
halt;
END;var
i, j, k, t, now, temp : longint;
BEGIN
read(leng, minstep, maxstep, n);
for i := 1 to n do
read(stone[i]);
if minstep = maxstep then special_judge;
for i := 1 to n-1 do
for j := i+1 to n do
if stone[j] < stone[i] then
BEGIN
temp := stone[i];
stone[i] := stone[j];
stone[j] := temp;
END;
n := n + 1;
stone[n] := leng;i := 1;
now := 0;
for i := 0 to maxstep do
f[i] := infinity;
f[maxstep] := 0;
now := 1;
i := 1;while now < leng-1 do
BEGIN
last := f;
for j := 0 to maxstep-1 do
f[j] := f[j+1];
f[maxstep] := infinity;
for j := 0 to maxstep-minstep do
if f[j] < f[maxstep] then f[maxstep] := f[j];
if now = stone[i] then
BEGIN
if (i < n) then f[maxstep] := f[maxstep] + 1;
i := i + 1;
now := now + 1;
continue;
END;if (i now) then now := stone[i] - 1
else now := now + 1;
END;ans := infinity;
for i := 1 to maxstep do
BEGIN
for j := 0 to maxstep-1 do
f[j] := f[j+1];
f[maxstep] := infinity;
for j := 0 to maxstep-minstep do
if f[j] < f[maxstep] then f[maxstep] := f[j];
if f[maxstep] < ans then ans := f[maxstep];
END;
writeln(ans);
END. -
0
panyihan2009 LV 9 @ 2009-11-03 21:22:59
这道题主要就是在压缩，动规部分并不难。
s=n,t>=n+1(n -
0
program river;
var
i,j,s,t,n,m,r,ans,tt:longint;
a,b:array[0..100] of longint;
f,g:array[-10..10010] of longint;
gg:array[-10..10010] of boolean;function min(x,y:longint):longint;
begin
if xb[j] then
begin
tt:=b[i];
b[i]:=b[j];
b[j]:=tt;
end;fillchar(a,sizeof(a),0);
fillchar(g,sizeof(g),0);for i:=1 to m do
begin
if b[i]-bf[i]) and (gg[i]=true) then ans:=f[i];
writeln(ans);
end;begin
fillchar(b,sizeof(b),0);
readln(n);
readln(s,t,m);
for i:=1 to m do read(b[i]);if s=t then work1
else work2;end.
请教压缩的原理
-
0
program p1002;
const verybig=5000;
var
data,flag,dp:array[1..3000]of longint;
i,j,s,t,p,q,min,l,m,count,ans:longint;
procedure qsort(p,q:longint);
var i,j,x,t:longint;
begin
if p>=q then exit;
i:=p;
j:=q;
x:=data[(i+j)shr 1];
while idp[j]+flag[i]
then dp[i]:=dp[j]+flag[i];
min:=verybig;
for i:=q to q+t+1 do if dp[i]
laiming
LV 4
@ 2013-06-20 13:28:38
