P1880 石子合併

来源:http://www.cnblogs.com/zwfymqz/archive/2017/05/27/6914447.html
-Advertisement-
Play Games

題目描述 在一個園形操場的四周擺放N堆石子,現要將石子有次序地合併成一堆.規定每次只能選相鄰的2堆合併成新的一堆,並將新的一堆的石子數,記為該次合併的得分。 試設計出1個演算法,計算出將N堆石子合併成1堆的最小得分和最大得分. 輸入輸出格式 輸入格式: 數據的第1行試正整數N,1≤N≤100,表示有N ...


題目描述

在一個園形操場的四周擺放N堆石子,現要將石子有次序地合併成一堆.規定每次只能選相鄰的2堆合併成新的一堆,並將新的一堆的石子數,記為該次合併的得分。

試設計出1個演算法,計算出將N堆石子合併成1堆的最小得分和最大得分.

輸入輸出格式

輸入格式:

數據的第1行試正整數N,1≤N≤100,表示有N堆石子.第2行有N個數,分別表示每堆石子的個數.

輸出格式:

輸出共2行,第1行為最小得分,第2行為最大得分.

輸入輸出樣例

輸入樣例#1:
4
4 5 9 4
輸出樣例#1:
43
54
一個簡單的石子合併我搞了一個晚上啊啊啊啊啊啊啊
枚舉區間l和r,分別取最大最小值
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=301;
 8 int n;
 9 int a[MAXN];
10 int dp[MAXN][MAXN];
11 int dp2[MAXN][MAXN];
12 int maxans=-1,minans=0x7ffff;
13 int read(int & n)
14 {
15        char c='/';int flag=0,x=0;
16        while(c<'0'||c>'9')
17        {c=getchar();}
18        while(c>='0'&&c<='9')
19        {x=(x<<3)+(x<<1)+(c-48);
20        c=getchar();}
21        n=x;
22 }
23 int main()
24 {
25     read(n);
26     //imemset(dp2,0xf,sizeof(dp2));
27     for(int i=1;i<=n;i++)
28     read(a[i]);
29     for(int i=1;i<=n;i++)
30         a[n+i]=a[i];
31     for(int i=1;i<2*n;i++)
32         a[i]+=a[i-1];
33     for(int i=2;i<=n;i++)
34         for(int l=1;l+i-1<n*2;l++)
35         {
36             int r=l+i-1;
37             dp[l][r]=0;
38             dp2[l][r]=0x7fffff;
39             for(int k=l;k<r;k++)
40                 {
41                     dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[r]-a[l-1]);
42                     //maxans=max(maxans,dp[i][j]);
43                     dp2[l][r]=min(dp2[l][r],dp2[l][k]+dp2[k+1][r]+a[r]-a[l-1]);
44                     //minans=min(minans,dp2[i][j]);
45                 }
46         }
47                 
48     
49     for(int i=1;i<=n;i++)
50     {
51         maxans=max(maxans,dp[i][i+n-1]);
52         minans=min(minans,dp2[i][i+n-1]);
53     }
54     printf("%d\n%d",minans,maxans);
55     return 0;
56 }

 








您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • C++編程模板2 ...
  • 遞歸C++ 一、遞歸簡介 自己調用自己 二、遞歸寫法 2.1 寫法介紹 先寫出問題的遞推公式 遞歸部分的邊界條件就是遞推公式中的邊界條件 遞歸部分的主體部分就是遞推公式中的主體部分 2.2 實例 (1)題目 例如:求n!。 (2)分析 遞歸公式為 f(n)=f(n-1)*n f(1)=1; 對應的遞 ...
  • 轉載請出自出處:http://www.cnblogs.com/hd3013779515/ 一、基本概念 1、redis集群是一個可以在多個節點之間進行數據共用的設施。redis集群提供了以下兩個好處1.1 將數據自動切分(split)到多個節點1.2 當集群中的某一個節點故障時,redis還可以繼續 ...
  • 遞推演算法 一、遞推演算法簡介 一般是兩步: 1、根據題目條件推出遞推公式 2、根據遞推公式編寫代碼求解(一般可以寫成普通迴圈和遞歸) 二、實例 2.1 斐波拉契數列 斐波拉契數列,1 1 2 3 5 8 13 21 34......,寫出第n項。 (1)遞推公式 f(n)=f(n-1)+f(n-2) ...
  • C++函數 一、函數簡介 函數就是方法,就是為了實現具體功能的一段代碼 二、函數結構 返回值類型 函數名(參數列表){ 函數體 } //求和函數 int sum(int a,int b){ return a+b;} 忘記函數結構怎麼寫的時候,就去想main函數結構,main函數總會寫吧 int ma ...
  • C++模板 C++信息學競賽編程模板 ...
  • 題目 synchronized怎麼實現線程同步?請修改《每天一道Java題[10]》中的MyRunnableThread類以解決三個線程都獲取到10的問題。 解答 方法一: 採用synchronized關鍵字包裹需要保證線程安全的代碼塊,來實現線程同步。語法格式為: 《每天一道Java題[10]》中 ...
  • 1.什麼是適配器模式? 適配器模式是一種過渡模式,用於溝通兩個不相容的事物,實現信息交換。 2.適配器模式的目的 使一個對象能夠以一種相對簡單的方式處理多個不同類型的對象,即一個對象相容多個不同類型的對象。例如,電腦接收外部硬體的插口唯一確定,不同尺寸的記憶體卡先插到讀卡器上,再由讀卡器插到唯一確定的 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...