当前位置: 首页 > news >正文

门户网站建设调查问卷b站网站推广mmm

门户网站建设调查问卷,b站网站推广mmm,wordpress开启gzip压缩,做网站设计师的原因将n(1≤n≤200)堆石子绕圆形操场摆放,现要将石子有次序地合并成一堆。 规定每次只能选相邻的两堆石子合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 (1)选择一种合并石子的方案,使得做n-1次合并,得分的总…

将n(1≤n≤200)堆石子绕圆形操场摆放,现要将石子有次序地合并成一堆。
规定每次只能选相邻的两堆石子合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 
(1)选择一种合并石子的方案,使得做n-1次合并,得分的总和最小。 
(2)选择一种合并石子的方案,使得做n-1次合并,得分的总和最大
输入
4
4 5 9 4
输出
43
54

线性结构是N个数据元素以有序的方式排列。访问线性结构一般采用由前至后的遍历方法。
线性动态规划就是在线性数据的基础上,通过某种递推方式(状态转移方程)得到最终结构的一种规划算法。
sum[i]: 从第1堆到第i堆石子数总和
fmax[i][j]: 从第i堆石子合并到第j堆石子的最大得分
fmin[i][j]: 从第i堆石子合并到第j堆石子的最小得分

初始化: fmax[i][i] = 0, fmin[i][i]= INF
状态方程:
fmax[i][j] = max{fmax[i][k]+fmax[k+1][j]+sum[j]-sum[i-1]} i <= k < j
fmin[i][j] = min{fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]} i <= k < j

由于题中围成一个环,我们将这条链再延长一倍,变成2*n堆,地中第i堆与第n+i堆相同,
动态规划求解后,答案为f(1,n), f(2,n+1), ... , f(n-1,2*n-2)中的最优解

状态转移
要计算f(i,j)的值时需知道所有f(i,k)和f(k+1,j)的值,
以len=j-i+1作为DP 的区间长度,从小到大枚举len,
然后枚举i的值,根据len和i用公式计算出j的值,然后枚举k,时间复杂度为O(n^3)

/*  https://loj.ac/problem/10147  */
#include <iostream>
using namespace std;

const int MAXN = 201;
const int INF = 0x3f3f3f3f;
int arr[2*MAXN];
int sum[2*MAXN];
int fmax[2*MAXN][2*MAXN];
int fmin[2*MAXN][2*MAXN];

int main()
{
    int i, j, k, n, len;
    cin >> n;
    for (i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        arr[n+i] = arr[i]; 
    }
    for (i = 1; i <=(n<<1); ++i)
        sum[i] = sum[i-1] + arr[i];

    for (len = 2; len <= n; ++len)
        for (i = 1; i <= (n<<1)-len+1; ++i)
        {
            j = i + len - 1;
            // 初始化
            fmax[i][j] = 0;
            fmin[i][j] = INF;
            for (k = i; k < j; ++k)
            {
                fmax[i][j] = max(fmax[i][j], fmax[i][k] + fmax[k+1][j] + sum[j] - sum[i-1]);
                fmin[i][j] = min(fmin[i][j], fmin[i][k] + fmin[k+1][j] + sum[j] - sum[i-1]);
            }
        }

    int ansmax = 0, ansmin = INF;
    for (i = 1; i < n; ++i)
    {
        ansmax = max(ansmax, fmax[i][i+n-1]);
        ansmin = min(ansmin, fmin[i][i+n-1]);
    }

    cout << ansmin << endl << ansmax << endl;


    return 0;
}


四边形不等式优化请参考

https://oi-wiki.org/dp/opt/quadrangle/

https://www.cnblogs.com/a1b3c7d9/p/10984353.html

dp[i][j]=min{dp[i][k]+dp[k+1][j]+w[i][j]} (i≤k<j)
把dp[i][k]+dp[k+1][j]取得最值的那个k, 称为dp[i][j]的最优决策点。

 

 

#include <iostream>
using namespace std;
const int MAXN = 201;
const int INF = 0x3f3f3f3f;
int arr[2*MAXN];
int sum[2*MAXN];
int fmax[2*MAXN][2*MAXN];
int fmin[2*MAXN][2*MAXN];
int ma[2*MAXN][2*MAXN]; //ma[i][j]: 从第i堆石子合并到第j堆石子的最大得分时的最优决策点
int mi[2*MAXN][2*MAXN]; //mi[i][j]: 从第i堆石子合并到第j堆石子的最小得分时的最优决策点

int main()
{
    int i, j, k, n, len, t;
    cin >> n;
    for (i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        arr[n+i] = arr[i];
    }
    for (i = 1; i <=(n<<1); ++i)
    {
        sum[i] = sum[i-1] + arr[i];
        ma[i][i] = i;
        mi[i][i] = i;
    }

    for (len = 2; len <= n; ++len)
        for (i = 1; i <= (n<<1)-len+1; ++i)
        {
            j = i + len - 1;
            // 初始化
            fmax[i][j] = 0;
            fmin[i][j] = INF;
            // 四边形不等式优化
            for (k = ma[i][j-1]; k <= ma[i+1][j] && k < j; ++k)
            {
                t = fmax[i][k] + fmax[k+1][j] + sum[j] - sum[i-1];
                if (fmax[i][j] < t)
                {
                    fmax[i][j] = t;
                    ma[i][j] = k;
                }
            }

            for (k = mi[i][j-1]; k <= mi[i+1][j] && k < j; ++k)
            {
                t = fmin[i][k] + fmin[k+1][j] + sum[j] - sum[i-1];
                if (fmin[i][j] > t)
                {
                    fmin[i][j] = t;
                    mi[i][j] = k;
                }
            }
        }

    int ansmax = 0, ansmin = INF;
    for (i = 1; i < n; ++i)
    {
        ansmax = max(ansmax, fmax[i][i+n-1]);
        ansmin = min(ansmin, fmin[i][i+n-1]);
    }

    cout << ansmin << endl << ansmax << endl;


    return 0;
}
 

http://www.mmbaike.com/news/110428.html

相关文章:

  • php建设网站后台北京搜索优化排名公司
  • wordpress设置投稿超级seo外链工具
  • 中国做外贸网站有哪些最新域名查询ip
  • 有人从搜索引擎找网站建设吗seo搜索引擎优化名词解释
  • 微网站建设微网站建设口碑营销案例简短
  • cdr 做网站页面技能培训班
  • 如何做网站的维护灰色词快速上排名
  • wordpress电商优秀上海做seo的公司
  • 做网站卖机器怎么弄大数据营销的概念
  • 什么网站可以销售自己的产品产品如何做网络推广
  • 建设局网站授权委托书搜索引擎优化特点
  • 酒店预定网站建设方案网店营销策划方案
  • 建站的平台下载百度 安装
  • 宝安石岩网站建设免费推广网站大全下载
  • 做计算机网站有哪些安卓手机优化软件哪个好
  • 怎样做带音乐的表白网站软件怎么推广
  • 电影网站做cpa2020国内十大小说网站排名
  • wordpress作者信息栏优化营商环境评价
  • 2b网站推广怎么做优秀网站设计欣赏
  • 石家庄网站建设远策科技做网站建设的公司
  • 人事怎么做招聘网站比对分析6个好用的bt种子搜索引擎
  • 贵州网站建设营销公司滨州seo排名
  • 百度站长工具有哪些长沙seo推广优化
  • 可以接单做网站的软件自己手机怎么免费做网站
  • 游戏平台代理东莞seo优化排名推广
  • wordpress上传出错北京网站建设优化
  • 档案网站建设的意义网店培训
  • 聊城 网站建设阿里云免费域名
  • 将制作好的网站上传去因特网自创网站
  • 微信微网站是什么格式的优化网站制作方法大全