题解 - Vijos

16

PowderHan LV 10 @ 2017-05-07 22:25:14

/*
一道经典的线性动态规划问题，其中也利用了一个贪心的思想。
核心：相邻最优+倒序处理
设f[I,j]为前i个人分成j 组的最小值，其中这里的前i个人为高度前i高的人，与题目的前i个人有所不同。
那么我们有这样的状态转移方程：
F[I,j]=Min{f[i-1][j], f[i-2][j-1]+(a[i]-a[i-1])^2}
说明一下：
1.这里的f[i-1][j]表示不以较矮身份分i号人到组中
2.f[i-2][j-1]表示以a[i], a[i-1]为两个较矮的人分成一组(即当前此人和后面的一个人一组)
显然，在排好序后，取a,b时取相邻的总比取不相邻的要好。
这样我们就可通过计算公式求出“残疾程度”，那么就可以了。
而f[i-3,j-1]即默认了a[i-2], a[i-1]与a[i]形成一组，实际上残疾程度的计算与最高的人没有任何关系
所以是f[i-2,j-1]！
最关键的需要注意DP的方向。。
由于题目升序排序。。故而当前第i人是最高的。。这样会发生一个很悲剧的情况：
很有可能最后的几个二元组找不到补齐的第三人。。所以我们需要把数据倒过来处理。。
即i循环来倒推
这样就算最后几个人组成若干二元组。。由于n>=3*m成立所以必然可以找到对应的第三人。。
(这段话好好理解，对dp有很大帮助)
在有了a,b后，中间的那个人c，需要c>a,c>b，所以c的下标必在a,b前面，又因为a和b相邻
因此循环的时候要有j<=min(m,(n-i+1)/3)。
最后答案就是f[1][m]
嗯表示还是要好好多明白题目意思扩展思路
涨姿势了Orz
我写的代码是从后往前倒序的，所以状态转移方程有所不同
好好体会吧~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

const int MAXN=5005;
int a[MAXN];
int f[MAXN][MAXN];//f[i][j]表示从后向前考虑到第i个人的时候分成j组的残疾程度最小值
int n,m;

void init()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}

void DP()
{
    memset(f,0x37,sizeof(f));
    for(int i=1;i<=n;i++)
        f[i][0]=0;
    for(int i=n-2;i>=1;i--)//我们可以在状态转移方程中看到，枚举的j其实是是否用来当三个人中最矮的一个，所以要从n-2开始才对
        for(int j=1;j<=min(m,(n-i+1)/3);j++)
            f[i][j]=min(f[i+1][j],f[i+2][j-1]+(a[i]-a[i+1])*(a[i]-a[i+1]));
    printf("%d\n",f[1][m]);
}

int main()
{
    init();
    DP();
}

4

ATHENS_ LV 9 @ 2017-11-01 20:16:15

题是简单，记得反向读入

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
long long dp[5005][1005];
int a[5005];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=n;i>=1;i--){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i<j*3)dp[i][j]=inf;
            else dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
        }
    }
    printf("%lld",dp[n][m]);
    
    return 0;
}

3

mufeng LV 7 @ 2017-10-08 21:36:38

f[i][j]=min(f[i-1][j],f[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));

这个状态转移方程前面的大大写的很详细了我就不再说了
有一点要注意的就是用这个方程需要先从身高高的开始
因为题目要求高的人站在中间两边的人比中间矮
由于题目要求升序输入就要用方法倒着将数据参与的方程中来
这样基本就可以过了

3

LXL LV 8 @ 2016-03-21 20:08:43

C++完美解题
#include <iostream>
using namespace std;
int m,n,a[10001],f[10001][2001];
int main()
{
cin>>m>>n;
for(int i=n;i>=1;i--)
cin>>a[i];
for(int i=1;i<=m;i++)
for(int j=3*i;j<=n;j++)
if(j==3*i)
f[j][i]=f[j-2][i-1]+(a[j]-a[j-1])*(a[j]-a[j-1]);
else
f[j][i]=min(f[j-1][i],f[j-2][i-1]+(a[j]-a[j-1])*(a[j]-a[j-1]));
cout<<f[n][m];
return 0;
}

2

nevets LV 7 @ 2012-07-22 17:23:30

用C++比用pascal的速度快。。

方程不难想。。f[i][j]=min(f[j], f[j-1]+sqr(a[i]-a))。。意义为前i人分为j组的最小代价。。显然。。对于第i人。。只能选择组队或者pass。。如果pass只能从f[j]转移。。如果组队显然只能和前一个组队。。故而从f[j-1]转移状态。。

但是！最关键的需要注意DP的方向。。由于题目升序排序。。故而当前第i人是最高的。。这样会发生一个很悲剧的情况：很有可能最后的几个二元组找不到补齐的第三人。。所以我们需要把数据倒过来处理。。这样就算最后几个人组成若干二元组。。由于n>=3*m成立所以必然可以找到对应的第三人。。

1

猫粮寸断 LV 10 @ 2018-09-06 15:00:21

大佬在上
发代码以示敬意

#include<iostream>
#include<cstring>
using namespace std;
int a[5010],dp[5010][1010];
int main()
{
    memset(dp,0x3f,sizeof(dp));
    int n,m,i,j;
    cin>>m>>n;
    for(i=1;i<=n;i++)
     cin>>a[i];
    dp[n][0]=0;
    dp[n-1][0]=0;
    for(i=n-2;i>0;i--)
    {
        dp[i][0]=0;
        for(j=1;j<=min(m,(n-i+1)/3);j++)
         dp[i][j]=min(dp[i+1][j],dp[i+2][j-1]+(a[i]-a[i+1])*(a[i]-a[i+1]));
    }
    cout<<dp[1][m];
    return 0;
}

1

Jessy LV 8 @ 2016-09-08 13:32:58

//只是个人当时的理解，如果有误，请勿喷，就是这样理解下吧，也有可能表诉不清请见谅
#include <iostream>
#include <cstdio>
#include <cstring>
#define M 2222
#define N 6666
#define MA 99999
using namespace std;
int n,m,a[N];
int f[N][M];
int main()
{
cin>>m>>n;
for (int i=n;i>=1;i--)
cin>>a[i];
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
f[i][j] = MA;
for (int i=1;i<=m;i++)
for (int j=i*3;j<=n;j++)//第j个人在第i组时有两种可能：边上或者中间，中间就与残疾程度无关了
f[j][i] = min(f[j-1][i],//与上次的站队方法做个比较
//也可以说是第j个人在站在两边的时候残疾程度会比上一次还大一些就选择上一次的,也可以说成让j站在中间
f[j-2][i-1]+(a[j]-a[j-1])*(a[j]-a[j-1]));//当前的残疾程度+上一组的的残疾程度，因为残疾程度只与站在两边的人有关，因此为 “-2”
//就是如果这个人站在两边，因为输入时升序排列，因此相邻的两个人一个人站一边时就是使残疾程度最小的
cout<<f[n][m]<<endl;
}

1

Pia LV 9 @ 2016-08-17 15:57:56

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

const int maxn = 10000 + 5;
const int INF = 1000000000;

int d[maxn][maxn/10], n, m, a[maxn];

int main(){
    freopen ( "in.txt" , "r" , stdin);
    cin >> m >> n;
    for (int i = 0; i < n; i++) cin >> a[n-i-1];
    
    for (int i = 1; i < n; i++) 
        for (int j = 0; j <= m; j++) 
            d[i][j] = INF;
    
    for (int i = 1; i < n; i++) 
        for (int j = 0; j <= min(m, (i+1)/3); j++) 
            d[i][j] = min (d[i-1][j], d[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
    
    cout << d[n-1][m];
    return 0;
}

0

Jong-oo LV 8 @ 2020-03-05 11:30:49

//循坏一直没弄出来, 感谢上面dalao
#include <iostream>         //迎春舞会之三人组舞
#include <algorithm>
#include <cstring>
using namespace std;
const int MaxN = 5005;

int m, n;
int num[MaxN];
int dp[MaxN][1005]; //dp[i][j] 前j个数选了i组
//  dp[i][j] = min(dp[i - 1][j], dp[i - 2][j - 1] + (num[i] - num[i - 1])*(num[i] - num[i - 1]));

void DP()
{
    memset(dp, 127, sizeof(dp));
    for (int i = 1; i <= n; i++)
        dp[i][0] = 0;
    for (int i = n - 2; i >= 1; i--)
        for (int j = 1; j <= min(m, (n - i + 1) / 3); j++)
            dp[i][j] = min(dp[i + 1][j], dp[i + 2][j - 1] + (num[i + 1] - num[i])*(num[i + 1] - num[i]));


    cout << dp[1][m];
}

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> num[i];
    DP();

    system("pause");
    return 0;
}

0

dkax LV 8 @ 2016-02-08 13:11:44

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int m, n;
int f[6007][1007], in[6007];
int main()
{
scanf("%d%d", &m, &n);
for(int i = n; i >= 1; i--)
scanf("%d", &in[i]);
memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n; i++)
f[i][0] = 0;
for(int i = 3; i <= n; i++)
for(int j = 1; j <= min(m, i / 3); j++)
f[i][j] = min(min(f[i - 1][j], f[i][j]), f[i - 2][j - 1] + (in[i] - in[i - 1]) * (in[i] - in[i - 1]));
/* for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cout << f[i][j] << " ";
}
cout << endl;
}*/
cout << f[n][m];
return 0;
}
庆祝30A

0

TenderRun LV 10 @ 2015-10-08 22:11:15

然而我并不怎么理解这一题

记录信息
评测状态 Accepted
题目 P1061 迎春舞会之三人组舞
递交时间 2015-10-08 22:10:28
代码语言 C++
评测机 VijosEx
消耗时间 332 ms
消耗内存 20100 KiB
评测时间 2015-10-08 22:10:30
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:13:6: warning: unused variable 'maxn' [-Wunused-variable]
int maxn=f[1][1];
^
测试数据 #0: Accepted, time = 15 ms, mem = 20100 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 20092 KiB, score = 5
测试数据 #2: Accepted, time = 15 ms, mem = 20092 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 20096 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 20092 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 20096 KiB, score = 5
测试数据 #6: Accepted, time = 15 ms, mem = 20092 KiB, score = 5
测试数据 #7: Accepted, time = 15 ms, mem = 20096 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 20100 KiB, score = 5
测试数据 #9: Accepted, time = 15 ms, mem = 20092 KiB, score = 5
测试数据 #10: Accepted, time = 15 ms, mem = 20096 KiB, score = 5
测试数据 #11: Accepted, time = 15 ms, mem = 20100 KiB, score = 5
测试数据 #12: Accepted, time = 15 ms, mem = 20092 KiB, score = 5
测试数据 #13: Accepted, time = 15 ms, mem = 20100 KiB, score = 5
测试数据 #14: Accepted, time = 15 ms, mem = 20096 KiB, score = 5
测试数据 #15: Accepted, time = 15 ms, mem = 20092 KiB, score = 5
测试数据 #16: Accepted, time = 31 ms, mem = 20100 KiB, score = 5
测试数据 #17: Accepted, time = 15 ms, mem = 20096 KiB, score = 5
测试数据 #18: Accepted, time = 31 ms, mem = 20100 KiB, score = 5
测试数据 #19: Accepted, time = 15 ms, mem = 20100 KiB, score = 5
Accepted, time = 332 ms, mem = 20100 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
int f[5010][1010];
int stu[5010];
int main()
{
int m,n;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d",&stu[i]);
int maxn=f[1][1];
memset(f,127,sizeof(f));
for(int i=1;i<=n;i++)
f[i][0]=0;
for(int i=n-2;i>=1;i--)
for(int j=1;j<=min(m,(n-i+1)/3);j++)
{
f[i][j]=min(f[i+1][j],f[i+2][j-1]+(stu[i]-stu[i+1])*(stu[i]-stu[i+1]));
}
printf("%d",f[1][m]);
}

0

sliverzero LV 8 @ 2010-04-02 14:04:59

有预感会因为和众大牛程序暗合而杯具……

很短很短的难度3

方程写对了就可以AC了，连预处理也几乎不用

0

hds108 LV 8 @ 2009-11-08 16:12:51

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

很简短的。。。。

var f:array[-1..10000,-1..10000] of longint;

a:array[-1..10000] of longint;

m,n,i,j:longint;

begin

readln(m,n);

for i:=n downto 1 do read(a[i]);

for i:=1 to n do for j:=1 to m do f:=99999999;

for i:=1 to n do for j:=1 to i div 3 do begin

f:=f;

if f>f+sqr(a-a[i]) then

f:=f+sqr(a-a[i]);

end;

writeln(f[n,m]);

end.

0

93狒狒 LV 9 @ 2009-11-02 23:32:31

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

记住，倒着做

0

芒果木瓜榴莲 LV 9 @ 2009-11-02 16:50:46

我本来以为我会动规了的说

做了这道水题，我傻了

我想知道，这个题边界是怎么弄的？

还有，vijos评测机最大能用多大内存？换成longint能开多大的数组？换成integer呢？

唉，不是学OI的料……

0

zhangyu16 LV 8 @ 2009-10-30 20:08:41

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 19：运行时错误...|错误号: 103

├ 测试数据 20：运行时错误...|错误号: 103

错误号: 103 =文件未打开

怎么会这样？

悲剧啊！！！

0

nemomojie LV 8 @ 2009-10-30 13:18:56

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

题目就是f[n,m]从n个人选m组人出来,其实就在于最后第n个用与否

所以,用f表示前i个人选出j组来

1.第i个人不用.那就是f的问题

2.第i个人用.那就是f+h(i,i-1)

从中选最优.

但由题目升序做的话.

第i个人就是目前最高的.

所以就算用了.

他也只能放在中间.

无法参与“残疾程度”h=(a-b)^2 的计算

所以就涉及到之前大牛们说的倒序来做

那样第i个人就是目前最矮的

就一定放在两边

而没有可能中间

这样就能做了

总的来说.倒序读入.

f:=min(f, 这里应该是 (i-1) div 3>=j 吧

f+sqr(a[i]-a))

i=1 to n

j=1 to i div 3

还有...

题目的范围真的有错

开大点的数组去避免下

0

3830372 LV 8 @ 2009-10-29 21:09:59

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

悲剧! 数组开错交了4次！

0

一Six个性 LV 8 @ 2009-10-29 17:12:11

我实在无语。。。。。。。。。。n

0

fenghao LV 10 @ 2009-10-27 01:50:13

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

没滚动就这效率了。。。时空复杂度O(n*m)，难度3有点高了。。估计noip也就这水平。。不过还是一次AC。。不错不错。。

注意到数据范围，很显然只能考虑n*m以下的复杂度，故考虑利用f表示前i个人选择j组所拥有的最小残疾程度。接下来考虑这样一个问题：是先确定中间还是先确定两边。由于最优结果由小个的差值决定，故应优先对小个进行规划。所以，应先对数据进行从大到小的有序化。之后，对于当前的i，只有两个状态：入选或者淘汰。当淘汰时，f=f，当入选时，f只与f有关（这里不是f，因为如果i入选，则i-1必然入选，即i与i-1构成一个残疾程度的二元组，中间最高的那个我们可以在前i-2个里面任选，由有序化数组性质知该命题成立）。

综上，f=min(f,f+sqr(a-a[i]))。

题解

153 条题解

迎春舞会之三人组舞

信息

状态

开发

支持

题解

153 条题解

迎春舞会之三人组舞

信息

状态

开发

支持

还没有账户？

登录