poj1160

逃离我推掉我的手 2022-06-18 04:19 135阅读 0赞

#include<iostream>  
    #include<string.h>  
    using namespace std;  
    int a[301];  
    __int64 cost[301][301];  
    __int64 dp[301][31];  
    int main()  
    {
          
        int v,p;  
        while(cin>>v>>p)  
        {
          
            for(int i=1;i<=v;i++)  
                cin>>a[i];  
            for(int i=1;i<=v;i++)  
                for(int j=1;j<=v;j++) cost[i][j]=999999999;  
            for(int i=1;i<=v;i++) cost[i][i]=0;  
            for(int i=1;i<=v;i++)  
                for(int j=i+1;j<=v;j++)  
                {
          
                    int mid=i+(j-i+1)/2;  
                    int sum=0;  
                    for(int k=mid-1;k>=i;k--)  
                        sum+=a[mid]-a[k];  
                    for(int k=mid+1;k<=j;k++)  
                        sum+=a[k]-a[mid];  
                    cost[i][j]=sum;  
                }  
            memset(dp,0,sizeof(dp));  
            for(int i=2;i<=v;i++)  
            {
          
                dp[i][1]=cost[1][i];  
                for(int j=2;j<=(i<p?i:p);j++)  
                {
          
                    dp[i][j]=999999999;  
                    for(int k=1;k<=i-1;k++)  
                    {
          
                        int c=dp[k][j-1]+cost[k+1][i];  
                        if(c<dp[i][j])  
                           dp[i][j]=c;  
                    }  
                }  
            }  
            cout<<dp[v][p]<<endl;  
        }  
        return 0;  
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 codevs1160 蛇形矩阵

题目描述 Description 小明玩一个数字游戏，取个n行n列数字矩阵（其中n为不超过100的奇数），数字的填补方法为：在矩阵中心从1开始以逆时针方向绕行，逐圈扩大，直到

冷不防/ 2024年02月17日 23:17/ 0 赞/ 76 阅读

相关 leetcode1160. 拼写单词

题目描述：给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某

迷南。/ 2023年07月16日 03:55/ 0 赞/ 14 阅读

相关 DP 【POJ1160】POST OFFICE 邮局问题

题意：在一个坐标轴上有n个村庄，每个村庄有一个坐标a\[i\]，现在要在这n个村庄之间建立m个邮局，求每个村庄到距离它最近的邮局的距离之和。其中n<=300,m<=30,1

约定不等于承诺〃/ 2022年08月18日 01:00/ 0 赞/ 182 阅读

相关 pku 1160 Post Office

\include <iostream> \include <cmath> \include <climits> using namespace std; int pos\[30

亦凉/ 2022年08月13日 16:49/ 0 赞/ 112 阅读

相关 UVA 1160——X-Plosives

题意：给定一些化合物（含有两个元素），当满足k个化合物且有k个元素的时候会发生爆炸，问多少个化合物是不能装车的。思路：并查集的简单应用。实际上满足条件的时候是一个

本是古典何须时尚/ 2022年07月29日 10:53/ 0 赞/ 6 阅读

相关 poj1160

include<iostream> include<string.h> using namespace std; int a[301

逃离我推掉我的手/ 2022年06月18日 04:19/ 0 赞/ 136 阅读

相关 HDU 1160 FatMouse's Speed

原题目链接：[HDU1160][] -------------------- 分类 HDU 动态规划最长上升子序列 --------------------

电玩女神/ 2022年04月15日 02:25/ 0 赞/ 181 阅读

相关 1160. Network

1160. Network Time limit: 1.0 second Memory limit: 64 MB Andrew is working as system

àì夳堔傛蜴生んèń/ 2022年01月05日 15:37/ 0 赞/ 284 阅读

相关 uva 1160 - X-Plosives

/\ 题意：往仓库里放\\\，把关键引爆\\\的数对拿出并计数数学模型：输入数对，判断是否成环eg（1,2 2,3 3,4, 1,4）这个时候要计数。该题中让人

末蓝、/ 2021年12月16日 19:05/ 0 赞/ 172 阅读

相关 hdu1160

[http://acm.hdu.edu.cn/showproblem.php?pid=1160][http_acm.hdu.edu.cn_showproblem.php_pid

￡神魔★判官ぃ/ 2021年10月19日 11:12/ 0 赞/ 230 阅读