题解 - Vijos

3

PowderHan LV 10 @ 2017-05-08 09:06:14

/*
两种做法   Orz反正我不会
第一
建棵树直接模拟即可，每次找花费最小的位置插入,结果是正确的
第二
动态规划
f[i][j]表示i个物品，使用j个指针的最小费用 
f[i][j]=min{f[j-1]+g[t][j]}
g[i][j]表示当前指针为j，使用了i个物品
g[i][j]=min{f[i][l]+p[j]*i*i)
初值f[1][1],g[1][x]
做到i时给f[1]赋值
于是复杂度就是O(n^2*k)
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <algorithm>
using namespace std;

int n,k,p[200],f[2000][200];

void init()
{
    memset(f,0,sizeof(f));
    memset(p,0,sizeof(p));
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= k; ++ i)
        scanf("%d",&p[i]);
    sort(p+1,p+1+k);
}

int mmin(int a,int b)
{
    if (a == 0)
        return b;
    else
        return min(a,b);
}

int dp(int x,int y,int l)
{
    if (x == 1)
    {
        f[x][y] = p[y];
        return f[x][y];
    }
    if (y == k)
    {
        f[x][y] = p[y] * x * x + dp(x,1,x-1);
        return f[x][y];
    }
    int temp;
    temp = k - y + 1;
    if (temp * l < x)
        return 0xFFFFFFF;
    if (f[x][y] != 0)
        return f[x][y];
    temp = (x-1) / (temp) + 1;
    for (int i = temp; i <= l; ++ i)
    {
        if (i == 1)
            f[x][y] = dp(x-1,y+1,x-2) + p[y];
        else
            f[x][y] = mmin( f[x][y] , dp(x-i,y+1,x-i-1) + dp(i,1,i-1) + i * i * p[y] );
    }
    return f[x][y];
}

int main()
{
    init();
    printf("%d",dp(n,1,n-1));
    return 0;
}

1

Sky1231 (sky1231) LV 10 @ 2017-01-27 20:50:41

#include <cstdio>
#include <algorithm>
#include <limits>
#define maxint (numeric_limits<int>::max)()/8
using namespace std;

int n,m,a[151],f[1001][151];

bool cmp1(int a,int b)
{
    return a<b;
}

int dfs1(int x,int y,int l)
{
    if (x==1)
    {
        f[x][y]=a[y];
        return f[x][y];
    }
    if (y==m)
    {
        f[x][y]=a[y]*x*x+dfs1(x,1,x-1);
        return f[x][y];
    }
    if ((m-y+1)*l<x)
        return maxint;
    if (f[x][y]!=maxint)
        return f[x][y];
    for (int i=(x-1)/(m-y+1)+1;i<=l;i++)
    {
        if (i==1)
            f[x][y]=dfs1(x-1,y+1,x-2)+a[y];
        else
            f[x][y]=min(f[x][y],dfs1(x-i,y+1,x-i-1)+dfs1(i,1,i-1)+i*i*a[y]);
    }
    return f[x][y];
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+m+1,cmp1);
    for (int i=0;i<=n;i++)
        for (int j=0;j<=m;j++)
            f[i][j]=maxint;
    printf("%d\n",dfs1(n,1,n-1));
}

sky1231 @ 2017-01-27 20:51:33

1800+MS
sky1231 @ 2017-02-01 13:10:22

1700+MS

1

stelan LV 7 @ 2008-12-13 00:29:26

好久没有切题了- -||

f[i][j]表示i个物品，使用j个指针的最小费用

f[i][j]=min{f[j-1]+g[t][j]}

g[i][j]表示当前指针为j，使用了i个物品

g[i][j]=min{f[i][l]+p[j]*i*i)

初值f[1][1],g[1][x]

做到i时给f[1]赋值

于是复杂度就是O(n^2*k)

0

BeastLu LV 9 @ 2015-05-06 22:23:53

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<memory.h>
#include<algorithm>
using namespace std;

int n,k,p[200],f[2000][200];

void init()
{
memset(f,0,sizeof(f));
memset(p,0,sizeof(p));
scanf("%d%d",&n,&k);
for (int i = 1; i <= k; ++ i)
scanf("%d",&p[i]);
sort(p+1,p+1+k);
}

int mmin(int a,int b)
{
if (a == 0)
return b;
else
return min(a,b);
}

int dp(int x,int y,int l)
{
if (x == 1)
{
f[x][y] = p[y];
return f[x][y];
}
if (y == k)
{
f[x][y] = p[y] * x * x + dp(x,1,x-1);
return f[x][y];
}
int temp;
temp = k - y + 1;
if (temp * l < x)
return 0xFFFFFFF;
if (f[x][y] != 0)
return f[x][y];
temp = (x-1) / (temp) + 1;
for (int i = temp; i <= l; ++ i)
{
if (i == 1)
f[x][y] = dp(x-1,y+1,x-2) + p[y];
else
f[x][y] = mmin( f[x][y] , dp(x-i,y+1,x-i-1) + dp(i,1,i-1) + i * i * p[y] );
}
return f[x][y];
}

int main()
{
init();
printf("%d",dp(n,1,n-1));
return 0;
}

0

415026664 LV 10 @ 2014-02-28 09:45:04

卧槽，啥坑爹题目= =，lazycal更本看不懂嘛╮(╯▽╰)╭

gconeice @ 2014-11-06 17:11:08

膜拜lazycal

0

vcvycy LV 8 @ 2013-07-06 19:53:57

方程f[i,j]表示有i个文件，这i个文件在某个等级的子目录中，只能往第j个指针即之后添加数（意思就是，1..j-1这几个指针都占用了）
优化：我们可以把指针大小从小到大排序下，越小的显然要加越多的文件。
不过加了这个优化也仅仅把10724 ms 优化到4246 ms～

上海红茶馆 - Windows Server 2003 via JudgeDaemon2/13.7.4.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 1312 ms, mem = 1256 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1232 KiB, score = 10
测试数据 #2: Accepted, time = 14 ms, mem = 1232 KiB, score = 10
测试数据 #3: Accepted, time = 136 ms, mem = 1240 KiB, score = 10
测试数据 #4: Accepted, time = 906 ms, mem = 1256 KiB, score = 10
测试数据 #5: Accepted, time = 1312 ms, mem = 1256 KiB, score = 10
测试数据 #6: Accepted, time = 2218 ms, mem = 1256 KiB, score = 10
测试数据 #7: Accepted, time = 1312 ms, mem = 1256 KiB, score = 10
测试数据 #8: Accepted, time = 1296 ms, mem = 1256 KiB, score = 10
测试数据 #9: Accepted, time = 2218 ms, mem = 1256 KiB, score = 10
Accepted, time = 10724 ms, mem = 1256 KiB, score = 100
上海红茶馆 - Windows Server 2012 via JudgeDaemon2/13.7.4.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 625 ms, mem = 1372 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1372 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1372 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 1372 KiB, score = 10
测试数据 #4: Accepted, time = 437 ms, mem = 1372 KiB, score = 10
测试数据 #5: Accepted, time = 609 ms, mem = 1372 KiB, score = 10
测试数据 #6: Accepted, time = 609 ms, mem = 1372 KiB, score = 10
测试数据 #7: Accepted, time = 671 ms, mem = 1372 KiB, score = 10
测试数据 #8: Accepted, time = 640 ms, mem = 1376 KiB, score = 10
测试数据 #9: Accepted, time = 609 ms, mem = 1372 KiB, score = 10
Accepted, time = 4246 ms, mem = 1376 KiB, score = 100

var
f:array[0..1001,0..151]of longint;
i,j,k,m,n,p:Longint;
a:array[0..151]of longint;
procedure init;
begin

read(n,k);
for i:=1 to k do
read(a[i]);
for i:=1 to k do
for j:=i+1 to k do
if a[i]>a[j] then
begin
p:=a[i];a[i]:=a[j];a[j]:=p;
end;
end;
function min(a,b:Longint):Longint;
begin

if (a>b)or(a=0) then exit(b);
exit(a);
end;
function dp(x,y,l:Longint):Longint;
var
i,j,p,mm,num:Longint;
begin
if x=1 then
begin
f[x,y]:=a[y];
exit(f[x,y]);
end;
if y=k then
begin
f[x,y]:=a[y]*x*x+dp(x,1,x-1);
exit(f[x,y]);
end;

num:=k-y+1;
if num*l<x then exit(maxlongint shr 2);

if f[x,y]<>0 then exit(f[x,y]);
mm:=(x-1)div (k-y+1) +1;
for i:=mm to l do
begin
if i=1 then
f[x,y]:=dp(x-1,y+1,x-2)+a[y]
else
f[x,y]:=min(f[x,y],dp(x-i,y+1,x-i-1)+dp(i,1,i-1)+i*i*a[y]);
end;
exit(f[x,y]);
end;
begin
init;

writeln(dp(n,1,n-1));
end.

0

cczzbb456 LV 8 @ 2010-07-04 10:22:27

这题最恶心的就是边界条件，DP方程很简单。

0

voyagec2 LV 10 @ 2009-11-09 18:17:46

模拟果然可以..

只是代码比DP长点

0

玛维-影之歌 LV 10 @ 2009-10-25 13:32:36

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

貌似DP很慢的说

不过时限12秒......连1s都没破

第40个......

0

ckl8520 LV 10 @ 2009-10-09 18:23:33

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

此题模拟才是王道，

时间O(N^2)

空间O(N)！！！！！

0

陈亮宇 LV 10 @ 2009-10-09 15:58:41

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

gaoji7777 LV 10 @ 2009-08-05 16:25:28

时间限制 Time Limitation

12S

...........

0

oimaster LV 10 @ 2009-07-09 21:49:29

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

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

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

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

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

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

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

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

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

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

居然全在1s内，puppy好强大！

题解（实际有的地方我自己还是不太明白）

0

寒蝉 LV 9 @ 2009-03-31 20:18:48

看了stelan 女王的，我AC了，成为第 16 个！

0

黄俊翔 LV 7 @ 2008-10-13 22:29:19

作者有才，打那么多

0

zyz915 LV 8 @ 2007-12-14 09:11:59

江苏2007省选第一轮居然直接拿这道题考我们。。。

建棵树直接模拟即可，每次找花费最小的位置插入,结果是正确的（我也不能证明）

当场做没想到动态规划，就这么模拟过了。。。

0

zxcvbnm16 LV 3 @ 2007-07-26 19:10:28

大牛们加油！

快做出呀！！

0

独角 LV 3 @ 2006-11-16 20:46:43

楼下的好帅啊～～～^-^

用DP方程的时候一定想清楚，每个量是由哪些量来推导的

还有就是要剪枝哦，不然的话单个数据都可能达到5000多ms

0

FancyMouse LV 3 @ 2006-10-19 20:36:13

总结：认真写DP方程，注意细节

P.S. 此题为湖南省选拔考HNOI2002 Day1 Problem2

P.P.S. 终于呆在Rank 1了，感觉好棒啊~.~

-1

LV 0 @ 2009-07-01 12:04:32

这么简单的题我都懒着去做，vijos的前途啊！！！

题解

20 条题解

HXOS

信息

状态

开发

支持

题解

20 条题解

HXOS

信息

状态

开发

支持

还没有账户？

登录