2

猫粮寸断 LV 10 @ 2018-09-04 21:37:07

裸DP，前缀和优化即可
部分式子进行了化简

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int sum[3010],dp[3010];
int main()
{
    memset(dp,0x3f,sizeof(dp));
    int n,d,i,j;
    char a;
    cin>>n>>d;
    for(i=1;i<=n;i++)
     {
        cin>>a;
        if(a=='H')
         sum[i]=sum[i-1]+1;
        else
         sum[i]=sum[i-1];
     }
    dp[0]=0;
    for(i=1;i<=n;i++)
     for(j=0;j<i;j++)
      if(int(abs(2*sum[i]-2*sum[j]-i+j))<=d||sum[i]-sum[j]==0||sum[i]-sum[j]==i-j)
        dp[i]=min(dp[i],dp[j]+1);
    cout<<dp[n];
    return 0;
}

2

mrsrz LV 10 @ 2017-02-04 14:50:43

开始想到了贪心，后来才发现思路是错的，于是想到dp
dp方程从之前的题解中找。
代码：
#include<cstdio>
#include<cstring>
#include<math.h>
#include<cctype>
#define C c=getchar()
using namespace std;
int f[2501],j[2501],h[2501];
int n,p;
int main(){
    scanf("%d%d",&n,&p);
    memset(j,0,sizeof(j));
    memset(h,0,sizeof(h));
    for(int i=1;i<=n;i++){
        char C;
        while(!isalpha(c))C;
        j[i]=j[i-1];
        h[i]=h[i-1];
        if(c=='J')j[i]++;else
        h[i]++;
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int k=1;k<=i;k++){
            int J=j[i]-j[k-1],H=h[i]-h[k-1];
            if(abs(J-H)<=p||J==0||H==0){
                if(f[i]>f[k-1]+1)f[i]=f[k-1]+1;
            }
        }
    }
    printf("%d\n",f[n]);
    return 0;
}

1

展翅雛龍 LV 10 @ 2009-10-30 19:53:18

f[i]表示前i个人需要多少辆车。

a[i]表示前i个人有多少人为H。

b[i]表示前i个人有多少人为J。

转移方程：

对于所有满足abs((a[i]-a[j])-(b[i]-b[j]))

0

z20c12h LV 9 @ 2017-07-18 18:38:56

这...我读错题了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define INF (0x3f3f3f3f)
using namespace std;
int n,d;
int hct[2510],jct[2510],dp[2510];
int main() {
    
    ios::sync_with_stdio(false);
    cin>>n>>d;
    for(int i=1;i<=n;i++) {
        char cc[6];
        cin>>cc;
        hct[i]=hct[i-1],jct[i]=jct[i-1];
        if (cc[0]=='H') hct[i]++;
        else jct[i]++;  
    }   
    memset(dp,INF,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
      for(int j=0;j<i;j++) 
        if (abs((hct[i]-hct[j])-(jct[i]-jct[j]))<=d
                    ||(hct[i]-hct[j]==0
                    ||jct[i]-jct[j]==0)) dp[i]=min(dp[i],dp[j]+1);
    cout<<dp[n]<<endl;  
    return 0; 
    
}

但没关系啦。

0

精Gang互撸娃 LV 6 @ 2016-07-14 18:16:33

Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(21,8) Warning: Variable "c" does not seem to be initialized
Linking foo.exe
24 lines compiled, 0.0 sec, 28288 bytes code, 1268 bytes data
1 warning(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 844 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 848 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 848 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 844 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 848 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 848 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 844 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 844 KiB, score = 10
Accepted, time = 105 ms, mem = 848 KiB, score = 100
program ball;
var a:array[1..2500]of char;
b,c:array[0..2500]of int64;
n,m,min:int64;
i,j:longint;
begin
assign(input,'ball.in');
assign(output,'ball.out');
reset(input);
rewrite(output);
readln(n,m);
b[0]:=0;
for i:=1 to n do
begin
readln(a[i]);
case a[i] of
'H':b[i]:=b[i-1]+1;
'J':b[i]:=b[i-1]-1;
end;
end;
for i:=1 to n do
begin
min:=maxlongint;
for j:=0 to i-1 do
if (abs(b[i]-b[j])<=m)or(abs(b[i]-b[j])=i-j) then
if min>c[j] then min:=c[j];
c[i]:=min+1;
end;
writeln(c[n]);
close(input);
close(output);
end.

0

913027135 LV 8 @ 2015-08-02 19:38:56

program a1331;
var
i,j,k,l,n,m,g,h,d,kk:longint;
c:array[0..2600]of longint;
f:array[0..5000]of longint;
ch:char;
function min(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;
begin
assign(input,'1.txt'); reset(input);
readln(n,d);
for i:=1 to n do
begin
readln(ch);
if ch='J' then
begin
inc(m);
c[i]:=m;
end
else
begin
dec(m);
c[i]:=m;
end;
end;
for i:=1 to n do
f[j]:=0;
for i:=1 to n do
begin
kk:=maxlongint;
for j:=0 to i-1 do
if (abs(c[i]-c[j])<=d)or(abs(c[i]-c[j])=i-j) then
if kk>f[j] then
begin
kk:=f[j];
if kk=0 then
break;
end;
f[i]:=kk+1;
end;
writeln(f[n]);
end.

0

913027135 LV 8 @ 2015-08-02 19:38:26

program a1331;
var
i,j,k,l,n,m,g,h,d,kk:longint;
c:array[0..2600]of longint;
f:array[0..5000]of longint;
ch:char;
function min(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;
begin
assign(input,'1.txt'); reset(input);
readln(n,d);
for i:=1 to n do
begin
readln(ch);
if ch='J' then
begin
inc(m);
c[i]:=m;
end
else
begin
dec(m);
c[i]:=m;
end;
end;
for i:=1 to n do
f[j]:=0;
for i:=1 to n do
begin
kk:=maxlongint;
for j:=0 to i-1 do
if (abs(c[i]-c[j])<=d)or(abs(c[i]-c[j])=i-j) then
if kk>f[j] then
begin
kk:=f[j];
if kk=0 then
break;
end;
f[i]:=kk+1;
end;
for i:=1 to n do
write(f[i],' ');writeln;
writeln(f[n]);
end.

0

风催林舞 LV 8 @ 2009-11-09 15:40:44

我被这个题彻底虐了，细节啊细节...

program cl(input,output);

var a:array[0..2500,1..2]of longint;

f:array[0..2500]of longint;

c:array[1..2500]of char;

n,d,i,j:longint;

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

begin

if x>y then exit(y)

else exit(x);

end;

begin

readln(n,d);

for i:=1 to n do

begin

readln(c[i]);

if c[i]='H' then inc(a);

if c[i]='J' then inc(a);

a:=a[i];

end;

for i:=1 to n do

f[i]:=10000000;

for i:=1 to n do

for j:=1 to i do

if (trunc(abs(a-a[j-1,1]-a+a[j-1,2]))

0

shenzheji LV 8 @ 2009-11-08 08:54:58

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第40道,纪念一下

0

Aries_C LV 9 @ 2009-11-02 18:17:56

-

一开始初始值赋太小了。。

0

lishunzhi LV 9 @ 2009-10-23 22:37:41

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var n,d,i,j:longint;

f:array[0..2502]of longint;

a,b:array[0..2502,0..2502]of longint;

x:array[0..2502]of char;

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

begin

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

end;

begin

readln(n,d);

fillchar(a,sizeof(a),0);

fillchar(b,sizeof(b),0);

for i:=1 to n do readln(x[i]);

for i:=1 to n do

for j:=i to n do

begin

a:=a;

b:=b;

if x[j]='H' then inc(a) else inc(b);

end;

f[1]:=1;

for i:=2 to n do

begin

f[i]:=99999999;

for j:=1 to i do

begin

if (abs(a[j,i]-b[j,i])

0

RayXie LV 8 @ 2009-10-22 21:19:05

注意f[0]=0

0

brace_123 LV 9 @ 2009-10-17 13:57:20

初始化和符号

要俺命也

0

student LV 8 @ 2009-10-15 20:58:13

郁闷~

水题罢了

0

lypkmy LV 8 @ 2009-10-05 14:04:10

AC........

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

*|\|\|\|\|\|\|\|\|\|\|\|\**|\*|

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

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

begin

readln(n,d);

for i:=1 to n do

begin

readln(s);

if s='H' then a[i]:=a+1 else a[i]:=a-1;

end;

f[1]:=1;

for i:=2 to n do

begin

f[i]:=maxint;

for j:=0 to i-1 do

begin

if (abs(a[i]-a[j])

0

nimo LV 8 @ 2009-10-04 11:18:38

编译通过...

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

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

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

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

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

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

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

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

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

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

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

【预处理】:

其中'J'=>a[i]=1 'H'=>a[i]=-1;

再统计：a[i]:=a[i]+a

【DP过程】:

for i:=1 to n do

　　p:=maxlongint;

　　for j:=0 to i-1 do

　　 if (abs(a[i]-a[j])f[j] then begin p:=f[j]; if p=0 then break; end;

　　f[i]:=p+1;

【条件的解释】

abs(a[i]-a[j])

0

lixiaomu3 LV 7 @ 2009-09-12 08:27:13

f[i]=min(f[k]+1)

且保证k+1至第i个人乘一辆巴士不会产生冲突

0

hxlong LV 10 @ 2009-09-06 16:33:25

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

秒杀

f[i]=min(f[k])+1;(0

0

peng7621260 LV 9 @ 2009-08-21 10:58:59

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

不降子序列的变形

0

xusc_2009 LV 9 @ 2009-08-17 10:48:39

一次AC总归是一件快乐的事情！

在思考中充分体会到了dp的思维灵活性，因为我原先想了一个O(n^3)然后一看铁定过不了，然后随便一改方程，就变成O(n^2)的了……

看到很多人写了，所以草草结束本次ac感言……

f[i]:=min(f[k])+1

O(n^2)预处理一下当前i~j是否可行

程序35行

题解

85 条题解

*|\|\|\|\|\|\|\|\|\|\|\|\**|\*|

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

f[i]:=p+1;

看球的巴士

信息

状态

开发

支持

题解

85 条题解

***|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\*|

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

f[i]:=p+1;

看球的巴士

信息

状态

开发

支持

还没有账户？

登录

*|\|\|\|\|\|\|\|\|\|\|\|\**|\*|

　　f[i]:=p+1;