题解 - Vijos

3

raffica LV 10 @ 2016-09-06 13:56:03

不是很懂怎么用DP，二分贪心水过。。。
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 560 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 564 KiB, score = 15
测试数据 #6: Accepted, time = 0 ms, mem = 564 KiB, score = 15
测试数据 #7: Accepted, time = 0 ms, mem = 560 KiB, score = 15
测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 15
测试数据 #9: Accepted, time = 0 ms, mem = 556 KiB, score = 15
Accepted, time = 15 ms, mem = 564 KiB, score = 100
```c++
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

int n, k;
int a[1010];
stack<int> stk;

inline bool check(int x) {
int i, cnt = 0, tmp = 0;
for(i = n-1;i >= 0;i --) {
tmp += a[i];
if(tmp > x) {
i ++;
tmp = 0;
cnt ++;
if(cnt >= k) return false;
}
}
return true;
}

inline void printAns(int x) {
int i, cnt = 0, tmp = 0;
stk.push(n);
for(i = n-1;i >= 0;i --) {
tmp += a[i];
if(tmp > x) {
i ++;
tmp = 0;
cnt ++;
stk.push(i+1);
stk.push(i);
}
}
stk.push(1);
while(!stk.empty()) {
printf("%d ", stk.top());
stk.pop();
printf("%d\n", stk.top());
stk.pop();
}
}

int main() {
int i, l, r, m;
scanf("%d%d", &n, &k);
for(i = 0;i < n;i ++) scanf("%d", a + i);
for(l = 1, r = 0x3f3f3f3f;l < r - 1;) {
m = (l + r) >> 1;
if(check(m)) r = m;
else l = m;
}
if(check(l)) printAns(l);
else printAns(r);
return 0;
}
```

1

Lifi LV 10 @ 2019-08-22 17:27:18

受到大佬启发，用了二分搜索。怎么改也改不对啊，后来才发现输出有问题。
如果这号人没有任务，那就不需要输出它的那一行。
样例如下，输入：

3 3
1 2 3

输出：

1 2
3 3

二分代码：

#include <iostream>

using namespace std;

typedef struct
{
    int a,b;
}pp;

int task[1001];
int n,m;
pp vp[1001]={0};

bool check(int x)
{
    int acc=0;
    int sum=0;
    int i;
    i=1;
    while(i<=n)
    {
        sum+=task[i];
        if(task[i]>x)
        {
            return false;
        }
        if(sum>x)
        {
            sum=0;
            acc++;
            continue;
        }
        i++;
    }
    if(sum!=0)
    {
        acc++;
    }
    if(acc<=m)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{
    cin>>n>>m;
    int i,j,k,l,sum;
    j=0;
    k=0;
    for(i=1;i<=n;i++)
    {
        cin>>task[i];
        j+=task[i];
    }
    i=0;
    while(i<=j)
    {
        k=(i+j)/2;
        if(check(k))
        {
            j=k-1;
        }
        else
        {
            i=k+1;
        }
    }
    if(check(i))
    {
        k=i;
    }
    else
    {
        k=j;
    }
    l=m;
    i=n;
    j=n;
    while(l>0)
    {
        sum=0;
        for(;i>0;i--)
        {
            sum+=task[i];
            if(sum>k)
            {
                break;
            }
        }
        vp[l].a=i+1;
        vp[l].b=j;
        j=i;
        l--;
    }
    for(i=1;i<=m;i++)
    {
        if(vp[i].a<=vp[i].b)
        {
            cout<<vp[i].a<<' '<<vp[i].b<<endl;
        }
    }
    return 0;
}

1

zxu22 LV 10 @ 2014-10-18 17:32:33

其实是二分查找加搜索吧，dp什么的时间复杂度不是很高吗？测试数据 #0: Accepted, time = 0 ms, mem = 828 KiB, score = 5

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

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

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

测试数据 #4: Accepted, time = 0 ms, mem = 832 KiB, score = 5

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

测试数据 #6: Accepted, time = 15 ms, mem = 824 KiB, score = 15

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

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

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

下面是代码。第一次写二分查找……调试了好久……好多冗余和负责的东西，大家见谅。
program a01;
var
i,m,n,add:longint;
ans,max,l,r:int64;
a:array[1..1005] of longint;

procedure found;
var
s,i:longint;
k:int64;
begin
k:=(l+r) div 2;
s:=0;
add:=0;
for i:= n downto 1 do
begin
if a[i]>k then begin
l:=k+1;
exit;
end;
if add+a[i]>k then begin
s:=s+1;
add:=a[i];
if s=m then begin
l:=k+1;
exit;
end
end
else add:=add+a[i];
end;

if s<m then begin
if ans>k then ans:=k;
r:=k;
end;
end;

procedure print(o:longint);
var
i,point:longint;
begin
if o=1 then begin
writeln(1,' ',o);
exit;
end;
point:=0;
add:=a[o];
for i :=o-1 downto 1 do
if add+a[i]>ans then begin
point:=i+1;
break;
end
else add:=add+a[i];
if (i=1)and(point=0) then begin
writeln(1,' ',o);
exit;
end;
print(point-1);
writeln(point,' ',o);
end;

begin
ans:=maxlongint;
read(n,m);
for i := 1 to n do
begin
read(a[i]);
max:=max+a[i];
end;
l:=1;
r:=max;
while r<>l do
found;
add:=0;
print(n);
end.

1

cl LV 7 @ 2009-08-27 08:43:38

哪位神牛解释一下

const maxm=1000;

var pre,a,ans:array[1..maxm] of longint;

l,r,mid,m,k,i:longint;

function ok(lim:longint):boolean;

var t,i,sum:longint;

begin

fillchar(pre,sizeof(pre),0);

pre[k+1]:=m+1;

t:=m;

for i:=k downto 1 do

begin

sum:=0;

while (t>0) and (sum+a[t]1 then exit(false) else

begin ans:=pre; exit(true); end;

end;

begin

readln(m,k);

for i:=1 to m do read(a[i]);

l:=-1;

r:=maxlongint>>1;

while r-l>1 do

begin

mid:=(r+l)>>1;

if ok(mid) then r:=mid else l:=mid;

end;

for i:=1 to k do

writeln(ans[i],' ',ans-1);

end.

0

zhengxiaohao LV 7 @ 2019-06-15 19:47:58

看到没有c++的dp题解，就过来了
首先DP方程如何推就不讲了,直接列出:dp[i][j]=min{max(dp[k][j−1],Sum[k+1,i])}(0≤k<i)
所以输出的时候就暴力输出,按题意要让后面多抄

#1 Accepted 4ms 7.988 MiB
#2 Accepted 4ms 7.961 MiB
#3 Accepted 4ms 8.027 MiB
#4 Accepted 8ms 8.082 MiB
#5 Accepted 19ms 8.086 MiB
#6 Accepted 4ms 8.074 MiB
#7 Accepted 176ms 8.094 MiB
#8 Accepted 99ms 8.094 MiB
#9 Accepted 17ms 8.074 MiB
#10 Accepted 23ms 8.07 MiB

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 1010
#define int long long
#define debug cout<<__LINE__<<" "<<__FUNCTION__<<"\n"

inline int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*y;
}
void put(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar((x%10)+48);
}
int a[N],dp[N][N];
void print(int x,int ans){
    if(!x) return;
    for(int i=x;i>=0;i--) {
        if(a[x]-a[i-1]>ans||i==0) {
            print(i,ans);
            cout<<i+1<<" "<<x;
            break;
        }
    }
    puts("");
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int n=read(),m=read();
    memset(dp,122,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++) a[i]=read()+a[i-1],dp[1][i]=a[i];
    for(int i=2;i<=m;i++){
        for(int j=i;j<=n;j++){
            for(int k=2;k<=j;k++){
                if(max(dp[i-1][k-1],a[j]-a[k-1])<dp[i][j]){
                    dp[i][j]=max(dp[i-1][k-1],a[j]-a[k-1]);
                }
            }
        }
    }
//  for(int i=1;i<=m;i++){
//      for(int j=1;j<=n;j++){
//          cout<<dp[i][j]<<" ";
//      }
//      cout<<"\n";
//  }
    print(n,dp[m][n]);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

0

葱_头 LV 10 @ 2009-08-27 17:25:03

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

1A

不用什么二分答案直接DP

而且很好写很短 ..

var

s:array[1..1000]of longint;

f,t:array[0..1000,0..1000]of longint;

mm:array[1..10000,1..2]of longint;

n,m:longint;

procedure init;

var

i,j,total:longint;

begin

readln(n,m);

if n=m then begin

for i:=1 to n do writeln(i,' ',i);

halt;

end;

for i:=1 to n do read(s[i]);

for i:=1 to n do begin

total:=0;

for j:=i to n do begin

inc(total,s[j]);

t:=total;

end;

end;

end;

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

begin

if x>y then exit(x);

exit(y);

end;

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

begin

if x>y then exit(y);

exit(x);

end;

procedure main;

var

i,j,k,x1,total,ans,r:longint;

begin

for i:=0 to n do f[0,i]:=10000000;

for i:=1 to m do

for j:=1 to n do begin

f:=t[1,j];

for k:=j-1 downto 1 do begin

if (t[k+1,j]>f) or (f>f)then break;

f:=min(f,max(f,t[k+1,j]));

end;

end;

ans:=f[m,n];

total:=0;

r:=n;

x1:=0;

for i:=n downto 1 do begin

inc(total,s[i]);

if total>ans then begin

inc(x1);

mm[x1,1]:=i+1;

mm[x1,2]:=r;

r:=i;

total:=s[i];

end;

end;

if total>=0 then begin

inc(x1);

mm[x1,1]:=1;

mm[x1,2]:=r;

end;

for i:=x1 downto 1 do

writeln(mm,' ',mm);

end;

begin

init;

main;

end.

-1

song19931218 LV 9 @ 2009-10-03 16:47:23

就用o(n^3)动规

-1

ufo172849z LV 10 @ 2009-09-03 14:14:08

那个“from飞过海”里的from拼错了。。。

还有时限问题：我用的是O(N^3)的。可是：

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

这。。。。？？？

-1

xyechang LV 10 @ 2009-08-27 17:32:28

编译通过...

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

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

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

├ 测试数据 04：答案错误...　├ 标准行输出 28 29

　├ 错误行输出 205 2....

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

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

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

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

├ 测试数据 09：答案错误...　├ 标准行输出 83 8...

　├ 错误行输出 324 ....

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

求助，有和我错的一样的吗？为什么？

-1

SuperTyphoon LV 8 @ 2009-08-27 16:46:10

How to DP ????

-1

_orz_ LV 10 @ 2009-08-27 16:09:35

不工作的居然不要输出~

-1

飞翔 LV 10 @ 2009-08-27 17:00:27

4 6 9 输出长，数据是何种类型，我为什么错啊

-1

wode LV 8 @ 2009-08-27 14:55:04

飞过海老兄，你心太狠，我交了六次，前五次结果如下：

编译通过... ├ 测试数据 01：答案错误...程序输出比正确答案长 ├ 测试数据 02：答案错误...程序输出比正确答案长 ├ 测试数据 03：答案错误...程序输出比正确答案长 ├ 测试数据 04：答案错误...程序输出比正确答案长 ├ 测试数据 05：答案错误...程序输出比正确答案长 ├ 测试数据 06：答案错误...程序输出比正确答案长 ├ 测试数据 07：答案错误...程序输出比正确答案长 ├ 测试数据 08：答案错误...程序输出比正确答案长 ├ 测试数据 09：答案错误...程序输出比正确答案长 ├ 测试数据 10：答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分：0 有效耗时：0ms 编译通过... ├ 测试数据 01：答案错误...程序输出比正确答案长 ├ 测试数据 02：答案错误...程序输出比正确答案长 ├ 测试数据 03：答案错误...程序输出比正确答案长 ├ 测试数据 04：答案错误...程序输出比正确答案长 ├ 测试数据 05：答案错误...程序输出比正确答案长 ├ 测试数据 06：答案错误...程序输出比正确答案长 ├ 测试数据 07：答案错误...程序输出比正确答案长 ├ 测试数据 08：答案错误...程序输出比正确答案长 ├ 测试数据 09：答案错误...程序输出比正确答案长 ├ 测试数据 10：答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分：0 有效耗时：0ms 编译通过... ├ 测试数据 01：答案错误...程序输出比正确答案长 ├ 测试数据 02：答案错误...程序输出比正确答案长 ├ 测试数据 03：答案错误...程序输出比正确答案长 ├ 测试数据 04：答案错误...程序输出比正确答案长 ├ 测试数据 05：答案错误...程序输出比正确答案长 ├ 测试数据 06：答案错误...程序输出比正确答案长 ├ 测试数据 07：答案错误...程序输出比正确答案长 ├ 测试数据 08：答案错误...程序输出比正确答案长 ├ 测试数据 09：答案错误...程序输出比正确答案长 ├ 测试数据 10：答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分：0 有效耗时：0ms 编译通过... ├ 测试数据 01：答案错误...程序输出比正确答案长 ├ 测试数据 02：答案错误...程序输出比正确答案长 ├ 测试数据 03：答案错误...程序输出比正确答案长 ├ 测试数据 04：答案错误...程序输出比正确答案长 ├ 测试数据 05：答案错误...程序输出比正确答案长 ├ 测试数据 06：答案错误...程序输出比正确答案长 ├ 测试数据 07：答案错误...程序输出比正确答案长 ├ 测试数据 08：答案错误...程序输出比正确答案长 ├ 测试数据 09：答案错误...程序输出比正确答案长 ├ 测试数据 10：答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分：0 有效耗时：0ms 编译通过... ├ 测试数据 01：答案错误...程序输出比正确答案长 ├ 测试数据 02：答案错误...程序输出比正确答案长 ├ 测试数据 03：答案错误...程序输出比正确答案长 ├ 测试数据 04：答案错误...程序输出比正确答案长 ├ 测试数据 05：答案错误...程序输出比正确答案长 ├ 测试数据 06：答案错误...程序输出比正确答案长 ├ 测试数据 07：答案错误...程序输出比正确答案长 ├ 测试数据 08：答案错误...程序输出比正确答案长 ├ 测试数据 09：答案错误...程序输出比正确答案长 ├ 测试数据 10：答案错误...程序输出比正确答案长 ------------------------- Unaccepted 有效得分：0 有效耗时：0ms

第六次，我赌上人品，一个字不改，他他他他----竟然过了!!!!!!!!!!!!!! {虽然没有秒杀}

varm,n,i,j,k,kk,l,x,y,z,o:longint;sum,f:array[-1..10000]of longint;p:array[-1..1200,-1..1200]of longint;function max(a,b:longint):longint;beginif a>b then max:=a else max:=b;end;function min(a,b:longint):longint;beginif a>b then min:=b else min:=a;;end;beginreadln(m,k);for i:=1 to m do beginread (z);sum[i]:=sum+z;if z>l thenl:=z;end;for i:=0 to m dofor j:=0 to m dop:=maxint;for i:=1 to k dofor j:=i to m-k+i dofor kk:=i-1 to j dop:=min(p,max(p,sum[j]-sum[kk-1]));i:=k;j:=m-1;o:=m;while j>0 dobeginwhile sum[o]-sum[j]

-1

BB牛 LV 8 @ 2009-08-27 09:34:31

二分答案=秒杀

-1

boyzkk LV 10 @ 2009-08-27 08:13:41

来自SPOJ.如果没看错的话。

-1

sifx_xu LV 10 @ 2009-08-27 01:39:46

编译通过...

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

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

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

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

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

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

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

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

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

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

O(N^3)的算法，不知道秒杀的大牛是用什么方法的?

DP求出最短时间，然后贪心，不知道为什么用单纯的DP只有20分，可以是我写错了～

-2

lishunzhi LV 9 @ 2009-10-18 12:12:00

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

................

-2

527971925 LV 10 @ 2009-09-07 00:14:18

明明就只是个动规...咋要搞的这么恼火......

老师布置了一道一样的题，交老师那能ac的题，到这里只有20分.....

我晕掉了，交了5次....

另外，庆祝一下，AC第100道题虽然很艰难....

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

-2

hxlong LV 10 @ 2009-09-05 18:07:46

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

SUNNY好慢啊

-2

oimaster LV 10 @ 2009-08-29 17:24:43

什么破题，输出可以少于k行（前面的人不干事就不用输出）……

二分答案+DP，还用了点单调性，复杂度O(31*m*k)……没秒掉……

题解

40 条题解

机密文件

信息

状态

开发

支持

题解

40 条题解

机密文件

信息

状态

开发

支持

还没有账户？

登录