石子合并--騰訊

題目描述:
小Q和牛博士在玩一個(gè)石子合并的游戲,初始一共有n堆石子耍休,每堆石子有w[i]個(gè)石子谋右。小Q和牛博士他們需要對(duì)石子堆進(jìn)行合并灶泵,每次他們可以任意選擇兩堆石子進(jìn)行合并育八。一堆有x個(gè)石子的石子堆和一堆有y個(gè)石子的石子堆合并將得到一堆x+y個(gè)石子的石子堆,這次合并得分為x*y赦邻,當(dāng)只剩下一堆石子的時(shí)候游戲結(jié)束髓棋。
小Q和牛博士希望采取優(yōu)秀的策略獲得最大得分,希望你能來幫他們算算最大得分多少惶洲。

image.png

image.png

思路:
可以發(fā)現(xiàn)不管合并的順序如何按声,結(jié)果都一致,所以以下代碼采用的是依次合并恬吕。
代碼:(C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a;
    vector<int> A(n);
    for(int i=0;i<n;i++)
    {
        cin>>a;
        A[i]=a;
    }
    int sum=0;
    for(int i=0;i<n-1;i++)
    {
        sum=sum+A[i]*A[i+1];
        A[i+1]=A[i]+A[i+1];
    }
    cout<<sum;
    return 0;
}

提交結(jié)果:

image.png

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末签则,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子币呵,更是在濱河造成了極大的恐慌,老刑警劉巖侨颈,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件余赢,死亡現(xiàn)場離奇詭異,居然都是意外死亡哈垢,警方通過查閱死者的電腦和手機(jī)妻柒,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來耘分,“玉大人举塔,你說我怎么就攤上這事∏筇” “怎么了央渣?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長渴频。 經(jīng)常有香客問我芽丹,道長,這世上最難降的妖魔是什么卜朗? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任拔第,我火速辦了婚禮咕村,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘蚊俺。我一直安慰自己懈涛,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布泳猬。 她就那樣靜靜地躺著批钠,像睡著了一般。 火紅的嫁衣襯著肌膚如雪暂殖。 梳的紋絲不亂的頭發(fā)上价匠,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音呛每,去河邊找鬼踩窖。 笑死,一個(gè)胖子當(dāng)著我的面吹牛晨横,可吹牛的內(nèi)容都是我干的洋腮。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼手形,長吁一口氣:“原來是場噩夢(mèng)啊……” “哼啥供!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起库糠,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤伙狐,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后瞬欧,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體贷屎,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年艘虎,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了唉侄。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡野建,死狀恐怖属划,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情候生,我是刑警寧澤同眯,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站唯鸭,受9級(jí)特大地震影響嗽测,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一唠粥、第九天 我趴在偏房一處隱蔽的房頂上張望疏魏。 院中可真熱鬧,春花似錦晤愧、人聲如沸大莫。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽只厘。三九已至,卻和暖如春舅巷,著一層夾襖步出監(jiān)牢的瞬間羔味,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國打工钠右, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留赋元,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓飒房,卻偏偏與公主長得像搁凸,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子狠毯,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 初始一共有n堆石子护糖,每堆石子有w[i]個(gè)石子,對(duì)石子堆進(jìn)行合并嚼松,每次任意選取兩堆石子進(jìn)行合并嫡良。一堆有x個(gè)石子的石子...
    Jacinth閱讀 454評(píng)論 0 1
  • 一年級(jí)語文上冊(cè)生字表 生字表一(共400字) 啊(ā)愛(ài)安(ān)岸(àn)爸(bà)八(bā)巴(bā)...
    meychang閱讀 2,806評(píng)論 0 6
  • sì 支zhī茶chá 對(duì)duì 酒jiǔ,賦fù 對(duì)duì 詩shī献酗,燕yàn子zi 對(duì)duì 鶯yīng 兒é...
    每個(gè)人的孟母堂閱讀 1,220評(píng)論 0 6
  • 概率論與數(shù)理統(tǒng)計(jì) 無窮小階數(shù) 無窮小量表述:線性逼近 相當(dāng)于利用切線和斜率來理解誤差和逼近寝受。 泰勒級(jí)數(shù):線性逼近 ...
    Babus閱讀 811評(píng)論 0 1
  • Zhōng huá zì jīng 中 華 字 經(jīng) dì yī bù fēn 第 一 部分 qián kūn yǒ...
    玉妖凰兒閱讀 2,732評(píng)論 0 9