首页 > 其他分享 >环形合并石子

环形合并石子

时间:2022-09-24 16:35:03浏览次数:48  
标签:10000 int 石子 合并 环形 include 1000

#include<iostream>
#include<cstring>
int f[1000][1000],s[10000],a[10000];
int k,n,maxn,miny=100000000;
using  namespace std;
int main()
{
    cin>>n;
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
        f[i][i]=0;        

    }
    for(int i=n+1;i<2*n;i++)
    {
        a[i]=a[i-n];
        s[i]=s[i-1]+a[i];
        f[i][i]=0;        
    }
//    len+l-1=j
    //j-l=len-1
    for(int len=2;len<=n;len++)
    {
        for(int l=1;len+l-1<=2*n;l++)
        {
            int r=l+len-1;
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
    miny=f[1][n];
    for(int i=2;i<=n;i++)
    {    
        miny=min(miny,f[i][i+n-1]);
    }
//    cout<<f[1][n]<<endl;
    cout<<miny<<endl;
    memset(f,0,sizeof(f));
    for(int len=2;len<=2*n;len++)
    {
        for(int l=1;len+l-1<=2*n;l++)
        {
            int r=l+len-1;
            for(int k=l;k<r;k++)
                f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
//    cout<<f[1][n];
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,f[i][i+n-1]);
    }
    cout<<maxn;
    return 0;
}

 

标签:10000,int,石子,合并,环形,include,1000
From: https://www.cnblogs.com/xdzxsuming/p/16725897.html

相关文章

  • 队列的模拟及环形队列思路
    定义队列是一个有序列表,可以用数组或是链表来实现。遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出模拟思路队列本身是有序列表,若使用数组的......
  • 合并两个顺序表
    合并两个顺序表已知有两个顺序表LA和LB(代码如下所示),并且两个表的储存的两个相邻元素,后者要大于或等于前者。合并这两个表。LA,LB的初始化#include<stdio.h>#defineMaxS......
  • 88. 合并两个有序数组
    题目给你两个按非递减顺序排列的整数数组 nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中,使合并后的数组同......
  • m3u8文件后缀jpg,png等处理方法及视频合并
    处理#解析伪装成png的tsdefresolve_ts(src_path,dst_path):'''如果m3u8返回的ts文件地址为https://p1.eckwai.com/ufile/adsocial/7ead0935-dd4f-4d2......
  • 前端合并单元格
     <!--合并单元格场景:将水平或垂直多个单元格合并成一个单元格1.明确合并哪几个单元格2.通过左上原则,确定保留谁删除谁上下合并-只保留最上的,删除其他左右合并-只......
  • Excel合并多个Excel工作簿
    Excel(powerquery)汇总多个Excel工作簿材料背景:多个Excel文件的表名(即字段)需要相同,如不相同,则会部分数据缺失需要被汇总的Excel文件放在同一个文件夹中,不需要放其他......
  • 力扣21(java&python)-合并两个有序链表(简单)
    题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1......
  • react-native 实现环形(圆形)进度条
    废话不多说,直接上硬货:效果图   安装 react-native-anchor-point用于处理旋转中心点位置yarnaddreact-native-anchor-pointgithub仓库地址: https://github......
  • 数组模拟环形队列
    简介对前面的数组模拟队列的优化,充分利用数组.因此将数组看做是一个环形的。(通过取模的方式来实现即可)代码实现importjava.util.Scanner;publicclassCir......
  • ES6合并数组并去重
    constdeps={'采购部':[1,2,3],'人事部':[5,8,12],'行政部':[5,14,79],'运输部':[3,64,105]}letmember=Object.values(deps).flat(Infin......