poj1045

ゝ一纸荒年。 2022-06-18 04:19 46阅读 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 条评论，46人围观）

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

相关阅读

相关 MySQL 1045登录失败

当你登录[MySQL][][数据库][MySQL]出现：Error 1045错误时（如下图），就表明你输入的用户名或密码错误被拒绝访问了，最简单的解决方法就是将MySQL数据库

深藏阁楼爱情的钟/ 2023年10月17日 13:04/ 0 赞/ 125 阅读

相关 1045 快速排序（JAVA）

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的 N 个互不

蔚落/ 2023年09月28日 18:34/ 0 赞/ 25 阅读

相关 MySQL主从同步 1045

请教mysql主从同步方式是否支持视图请教mysql主从同步方式是否支持视图 \--主机开两个窗口，一个进入mysql，一个是shell--主机阻断写操作mysql>

墨蓝/ 2023年09月25日 09:53/ 0 赞/ 4 阅读

相关 mysql 1045 错误

mysql 密码错误 ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using passwo

喜欢ヅ旅行/ 2023年02月17日 13:26/ 0 赞/ 49 阅读

相关 Fire Net--hdu1045

Fire Net Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

骑猪看日落/ 2022年08月04日 08:57/ 0 赞/ 168 阅读

相关 hdoj1045

Fire Net Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

你的名字/ 2022年08月03日 11:59/ 0 赞/ 51 阅读

相关 poj1045

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

ゝ一纸荒年。/ 2022年06月18日 04:19/ 0 赞/ 47 阅读

相关 HDU 1045

[Fire Net][] Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

清疚/ 2022年06月17日 01:29/ 0 赞/ 88 阅读

相关 1045. 快速排序(25)

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的N个互不相同的

蔚落/ 2022年05月26日 07:18/ 0 赞/ 168 阅读

相关 PAT乙级1045

1045 快速排序（25 分）著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到

蔚落/ 2022年05月11日 15:14/ 0 赞/ 160 阅读