acm動態規劃題
1樓：逸
這是動態規劃很經典的問題之一。。。
還有，想糾正lz乙個說法，「用c做，怎麼做？不行的話c++也行啊」，感覺lz覺得c++更厲害一些哈。。。其實不然，像lz說的這種問題是演算法問題，不基於某種程式語言的。。。
正題：假設我們的例項是：
我們可以用乙個整型陣列max來存狀態（這裡就是動態規劃），這個狀態就是從頂上走到當前數字num[i][j]時和最大的那個和max[i][j]
程式執行完例子後，max中為這樣的：
程式如下：#include
#include
#define max 100
int num[max][max];
int max[max][max];
int n;
int main()
for (i=0; ifor (i=0; i// 輸出max值。
max = max[n-1][0];
for (i=1; iif (_max < max[n-1][i])_max = max[n-1][i];
printf("%d", _max);
system("pause");
return 0;}
2樓：網友
思路是這樣的。
三角形中每乙個點都可以從上層的兩個點到達該點，假如我們知道頂點分別到上層兩個點的最優路徑，選擇數字之和最大的那條路徑就是頂點到該點的最佳路徑，也就是說如果我們知道頂點到第n層中每乙個點的最佳路徑，那麼我們就可以求出頂點到第n+1層中每乙個點的最佳路徑，而第一層是最優路徑是已知的，最終的結果就是從底層的n條路徑中選乙個數值最大的就是答案。
3樓：網友
給樓主提供另乙個思路。
楊輝三角 計算權值。
求動態規劃題目（acm或oi的）要求必須有資料！
4樓：網友
背景：某電力系統擬建三座大型水電站，通過設計負荷水平年和枯水年的電力電量平衡計算，確定水電站群的**機容量為280萬kw；根據投資估算和經濟分析，各電站可選擇的裝機容量變化範圍及部分裝機容量相應的費用列表如下：
費用。億元)
序號 裝機容量(萬kw)
電站1電站2
電站3問題：如何合理地分配水電站群內各電站的裝機容量，使系統的總費用為最小？
求acm競賽關於動態規劃中的揹包問題的onlinejudge的題，越多越好，寫明是哪個學校的哪道題，越多越好。
5樓：
如果真的想練習dp題目的話，那麼到hust 的 virtual judge 上面的contest搜尋一下就有很多揹包的題目了。在hdu的 diy 也可以找到很多。 感覺這些練練就夠了吧。
關於acm的深搜和廣搜以及動態規劃
6樓：奮鬥的雨滴
你好，親，這段講解使我們集訓隊代課老師給我們的，希望有幫助。
bfs與dfs的討論：bfs：這是一種基於佇列這種資料結構的搜尋方式，它的特點是由每乙個狀態可以擴充套件出許多狀態，然後再以此擴充套件，直到找到目標狀態或者佇列中頭尾指標相遇，即佇列中所有狀態都已處理完畢。
dfs：基於遞迴的搜尋方式，它的特點是由乙個狀態拓展乙個狀態，然後不停拓展，直到找到目標或者無法繼續拓展結束乙個狀態的遞迴。
優缺點：bfs:對於解決最短或最少問題特別有效，而且尋找深度小，但缺點是記憶體耗費量大（需要開大量的陣列單元用來儲存狀態）。
總結：不管是bfs還是dfs，它們雖然好用，但由於時間和空間的侷限性，以至於它們只能解決資料量小的問題。
座標型別搜尋 ：這種型別的搜尋題目通常來說簡單的比較簡單，複雜的通常在邊界的處理和情況的討論方面會比較複雜，分析這類問題，我們首先要抓住題目的意思，看具體是怎麼建立座標系（特別重要），然後仔細分析到搜尋的每乙個階段是如何通過條件轉移到下乙個階段的。確定每一次遞迴（對於dfs）的回溯和深入條件，對於bfs，要注意每一次入隊的條件同時注意判重。
要牢牢把握目標狀態是乙個什麼狀態，在什麼時候結束搜尋。還有，dfs過程的引數如何設定，是帶引數還是不帶引數，帶的話各個引數一定要保證能完全的表示乙個狀態，不會出現乙個狀態對應多個引數，而這一點對於bfs來說就稍簡單些，只需要多設定些變數就可以了。
經典題目：細胞（ndk1435）、tyvj：乳草的入侵、武士風度的牛。
數值型別搜尋：（雖然我也不知道該怎麼叫，就起這個名字吧），這種型別的搜尋就需要仔細分析分析了，一般來說採用dfs，而且它的終止條件一般都是很明顯的，難就難在對於過程的把握，過程的把握類似於座標型別的搜尋（判重、深入、列舉），注意這種型別的搜尋通常還要用到剪枝優化，對於那些明顯不符合要求的特殊狀態我們一定要在之前就去掉它，否則它會像滾雪球一樣越滾越大，浪費我們的時間。
你好，明天可以發你幾道這類題，而且還有**，親。
西南交大acm1001 題，vs2008驗證正確，為什麼oj執行結果錯誤
7樓：網友
edwardvsnc 1001 wrong answer g++
我交了一下，說是wrong answer 說明你的程式有問題他有一些資料通過你的程式得到了錯誤的結果，說明你的程式在一些地方有問題。
你可以看看邊界資料有沒有問題，比如說 1， 0， 10000什麼的。
acm試題，要用動態規劃解決，c或c++的程式
8樓：網友
是乙個揹包，可以去學習一下。
#include
#include
const int max=1005;
int dp[max];
int v,p;
int main()
printf("%d",dp[n]);
return 0;}
關於西南交大2 ，關於西南交大2 2！
關於中法 4 4 補充樓上幾點 1 西南交大中法 4 4 計劃只限於土木 機械 電氣 資訊等幾個工科學院 2 赴法學生在大二下學期選拔，條件是前三個學期的成績和英語水平，競爭激烈 3 在法國完成後兩年學習後，自動獲得西南交大免試研究生資格，回國後不一定要讀原專業，可在學校所有研究生專業中任選 4 參...
西南交大西班牙留學專案，西南交大南韓西班牙留學怎麼樣
別提了，一想到我就火氣大，真的是，我是年的時候在他們報的西班牙，我都簽了幾次了，還沒給我簽過。正打算找他們賠償我損失，把我給害的。老師們意味的吹噓時間短，但是半年的西語學習根本不好通過簽證，然後給我保證能夠上到西班牙最好的大學，但是已經到西班牙的同學每有乙個進入最好的大學的，然後找到他們理論，結果他...
西南交大峨眉校區
游泳是必須學的，大一下期開始有，另外還要選擇體育子專案。軍訓的話，以前都是在一個機場，近幾年開始把軍訓安排在大一結束的暑假。而今年我們是在學校進行的軍訓，7月12號到7月23號 具體什麼時間應該不定，但時長為12天左右 開學考英語是為了分英語班，絕大部分的同學分在b類班級，是一般的教學班，英語特別好...