uva 10271 Chopsticks 【dp】

Myth丶恋晨 2022-08-12 16:19 145阅读 0赞

题目：uva 10271Chopsticks

题意：从一组数中选出每三个为一组，价值为三个中两个小的差值的平方和，让这个总价值最小。

分析：定义dp【i】【j】为从后 i 个中选出 j 对的最小价值。

转移方程：dp【i】【j】 = min（dp【i-1】【j】，dp【i+2】【j-1】+（a【i】-a【i+1】）\*（a【i】-a【i+1】））

注意状态转移的条件：就是每组要保留一个最大的值作为第三个值。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <queue>
    typedef long long ll;
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 5500;
    int a[N];
    int dp[N][2000];
    int cmp(int x,int y)
    {
        return x>y;
    }
    int main()
    {
        int pro,n;
        while(~scanf("%d%d",&pro,&n))
        {
            memset(dp,inf,sizeof(dp));
            for(int i=n; i>=1; i--)
                scanf("%d",&a[i]),dp[i][0]=0;
            sort(a+1,a+n+1,cmp);
            for(int i=3;i<=n;i++)
            {
                for(int j=1;j<=min(pro,i/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]));
            }
            printf("%d\n",dp[n][pro]);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 116 Unidirectional TSP(dp)

分析：本题中每一列就是一个阶段，每个阶段有三种决策；状态方程dp\[i\]\[j\]=min(dp\[i-1\]\[j+1\],dp\[i\]\[j+1\],dp\[i+1\]

比眉伴天荒/ 2024年02月17日 19:29/ 0 赞/ 46 阅读

相关 uva 10271——Chopsticks

题意：有n只筷子，然后选出来k+8套（一套有三只，分别ABC），一套筷子质量为最小的两只的平方，选出的使得总的质量和最小。思路：01背包。dp\[i\]\[j\]

逃离我推掉我的手/ 2022年08月18日 11:32/ 0 赞/ 16 阅读

相关 uva 10271 Chopsticks 【dp】

题目：uva 10271Chopsticks 题意：从一组数中选出每三个为一组，价值为三个中两个小的差值的平方和，让这个总价值最小。分析：定义dp【i

Myth丶恋晨/ 2022年08月12日 16:19/ 0 赞/ 146 阅读

相关数位DP UVA - 11038

数位DP，顾名思义，是在个位，十位，百位，千位…….这些数的数位上进行的DP，它其实就是一种暴力枚举+记忆化搜索。数位DP一般用来解决要求找出某个区间内，满足要求的数有多

ゝ一纸荒年。/ 2022年06月09日 00:29/ 0 赞/ 283 阅读

相关 TOJ 2865 Chopsticks DP

2865: Chopsticks 描述 In China, people use a pair of chopsticks to get food on the tab

拼搏现实的明天。/ 2022年05月17日 02:38/ 0 赞/ 112 阅读

相关 DP-UVA 10036-Divisibility

DP-UVA 10036-Divisibility -------------------- 题目链接： [10036 - Divisibility

桃扇骨/ 2022年05月14日 22:22/ 0 赞/ 144 阅读

相关 uva 10721 - Bar Codes(dp)

[题目链接：uva 10721 - Bar Codes][uva 10721 - Bar Codes] 题目大意：给出n，k和m，用k个1~m的数组成n，问有几种组

蔚落/ 2022年05月12日 23:34/ 0 赞/ 147 阅读

相关 uva-10828 期望dp+gauss

[传送门][Link 1] 题意：给你一个有向图，从1号节点出发，问经过某个点的期望次数。思路：传递闭包写错wa到哭。设 dp\[i\]为经过i点期望 dp\[v\]=

浅浅的花香味﹌/ 2022年05月09日 11:08/ 0 赞/ 172 阅读

相关 UVA 10003 区间DP

题意：有一根长度为l的木棍，木棍上面有m个切割点，每一次切割都要付出当前木棍长度的代价，问怎样切割有最小代价。分析：石子合并的逆过程。状态：设F（i，j）为区间(

绝地灬酷狼/ 2021年12月18日 15:19/ 0 赞/ 272 阅读

相关 uva10859 (树形dp)

题意：给你一个ｎ个点ｍ条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。在灯的总数最小的前提下，被两盏灯同时被照亮的边数应该尽量

青旅半醒/ 2021年12月14日 03:21/ 0 赞/ 358 阅读