uva 10271——Chopsticks

逃离我推掉我的手 2022-08-18 11:32 16阅读 0赞

题意：有n只筷子，然后选出来k+8套（一套有三只，分别ABC），一套筷子质量为最小的两只的平方，选出的使得总的质量和最小。

思路：01背包。dp\[i\]\[j\]表示j套利选出来i套的最优解，每个都有选当前和不选当前两中状态。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=6005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,t) for (int i=s;i>=t;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int n,k,T;
    int v[M],dp[M][M];
    int main()
    {
        scanf("%d",&T);
        ft(ca,1,T){
            scanf("%d %d",&k,&n);k+=8;
            frt(i,n-1,0) scanf("%d",&v[i]);
            ft(i,1,k) ft(j,0,n){
                dp[i][j]=0;
                if (i*3>j){dp[i][j]=9999999;continue;}
                dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+(v[j-1]-v[j-2])*(v[j-1]-v[j-2]));
            }
    
            printf("%d\n",dp[k][n]);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 WebLogic XMLDecoder反序列化漏洞(CVE-2017-10271)

文章目录声明一、WebLogic介绍二、WebLogic XMLDecoder漏洞产生原因三、漏洞影响版本四、漏洞利用路径

素颜马尾好姑娘i/ 2024年04月01日 17:30/ 0 赞/ 77 阅读

相关 uva 10271——Chopsticks

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

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

相关 uva 10271 Chopsticks 【dp】

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

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

相关 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 阅读

相关 UVA 414

include<iostream> include<string> include<cstring> using namespace std;

╰半夏微凉°/ 2021年11月17日 21:36/ 0 赞/ 299 阅读

相关 UVA 621

include<iostream> include<string> using namespace std; int main() {

朴灿烈づ我的快乐病毒、/ 2021年11月17日 21:33/ 0 赞/ 253 阅读

相关 Uva 540

include<iostream> include<queue> include<cstring> include<string> us

Love The Way You Lie/ 2021年11月17日 21:20/ 0 赞/ 342 阅读

相关 uva 127

开始用的是vector<sta include<iostream> include<cstring> include<vector> incl

快来打我*/ 2021年11月17日 21:18/ 0 赞/ 265 阅读

相关 UVA Intervals

UVA Intervals Description 有n个区间，在区间\[ai，bi\]中至少取任意互不相同的ci个整数。求在满足n个区间的情况下，至少要取多

你的名字/ 2021年11月10日 02:26/ 0 赞/ 277 阅读

相关 cve-2017–10271 XMLDecoder 反序列化漏洞原理分析

目录 1.漏洞背景 2.漏洞原理分析 3.漏洞测试环境搭建漏洞复现 4.修复建议 -------------------- 1.漏洞背景 Weblog

迈不过友情╰/ 2021年09月01日 00:04/ 0 赞/ 1177 阅读