weixin_41429120
weixin_41429120
2021-05-09 14:23
采纳率: 100%
浏览 72

请教一下这道C++题,NOIP,急急急 加急

  • 点赞
  • 收藏

4条回答 默认 最新

  • qq_42145681
    白驹_过隙 2021-05-09 14:45
    已采纳
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    
    const int maxn=330;
    int dp[maxn][maxn];
    int a[maxn];
    int dis[maxn][maxn];//dis[i][j]表示在第i个村和第j个村之间建一个邮局的“代价”
    
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            //预处理dis[i][j]
            for(int i=1;i<=n;i++)
                for(int j=i+1;j<=n;j++)
            {
    
                //显然在[i,j]放一个邮局,放在最中间是最优的
                dis[i][j]=dis[i][j-1]+a[j]-a[(i+j)/2];
            }
            for(int i=1;i<=n;i++)
            {
                dp[i][i]=0;
                dp[i][1]=dis[1][i];
            }
            for(int j=2;j<=m;j++)
            {
                for(int i=j+1;i<=n;i++)
                {
                    dp[i][j]=INF;
                    for(int k=j-1;k<i;k++)
                    {
                        dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]);
                    }
                }
            }
            printf("%d\n",dp[n][m]);
        }
        return 0;
    }
    点赞 1 评论
  • it_xiangqiang
    C和C++技术博客 2021-05-09 22:56

      希望对你有帮助:https://blog.csdn.net/it_xiangqiang/category_10768339.html

    点赞 评论
  • QA_Assistant
    有问必答小助手 2021-05-10 11:03

    您好,我是有问必答小助手,您的问题已经有小伙伴解答了,您看下是否解决,可以追评进行沟通哦~

    如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~

    ps:问答VIP仅需29元,即可享受5次/月 有问必答服务,了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632

    点赞 评论
  • QA_Assistant
    有问必答小助手 2021-05-11 15:51

    非常感谢您使用有问必答服务,为了后续更快速的帮您解决问题,现诚邀您参与有问必答体验反馈。您的建议将会运用到我们的产品优化中,希望能得到您的支持与协助!

    速戳参与调研>>>https://t.csdnimg.cn/Kf0y

    点赞 评论

相关推荐