1.石子合并
任務描述
沿著河岸擺放 N 堆石子，現(xiàn)要將石子有次序地合并成一堆，規(guī)定每次只能選相鄰的 2 堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。 例如:4堆石子4,5,9,4，可以按(((4,5),9),4)合并。
- 第一次合并得分是
9分，合并之后石子堆是9,9,4 - 第二次合并得分是
18分，合并之后石子堆是18,4 - 第三次合并得分是
22分，合并之后石子堆是22 - 三次合并總得分
49
試設計出一個算法,計算出將 N 堆石子合并成 1堆的最小得分和最大得分。
測試說明
輸入格式
數(shù)據(jù)的第 1行是正整數(shù) N，表示有N 堆石子。
第 2行有 N 個整數(shù)，第i 個整數(shù) ai? 表示第i 堆石子的個數(shù)。
輸出格式
輸出共 2 行，第 1 行為最小得分，第 2行為最大得分。
樣例輸入
4 4 5 9 4
樣例輸出
44 54
提示
1≤N≤100，0≤ai?≤20。
思路：
例如:4堆石子4,5,9,4?
要知道從開頭4合并到最后4的最小代價，就需要知道從4合并到9的最小代價再合并最后一個4.....由此知道遞推關系：
dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] + dpmin[k + 1][j] + sum*[i->j]);
其中d[i][j]表示把第i到j堆合并成一堆的最小代價，sum*[i->j]表示第i到第j堆的石子數(shù)量之和。
由轉(zhuǎn)移方程，可以看出要按照長度j－i進行迭代求解。
?dpmax也是一樣，只是把每次找最小值改為每次取最大值。
?注：主函數(shù)中數(shù)組是從1開始存的不是0?。?！
代碼：
#include <iostream>
#include <algorithm>
using namespace std;
//在主函數(shù)中數(shù)組下標是從1開始的
void dpStone(int a[],int n)
{
/********** Begin **********/
//補充代碼完成功能
const int INF = 0x3f3f3f3f;
int dpmin[100][100], sum[100], dpmax[100][100];
dpmin[n][n] = { {0} };//將數(shù)組初始化
dpmax[n][n] = { {0} };
sum[n] = { 0 };
sum[1] = a[1];//設置第一個石子數(shù)量
for (int i = 2; i <= n; i++)
{
sum[i] = sum[i - 1] + a[i];//存從1到i的石子數(shù)量和
}
for (int v = 1; v <= n; v++) // 表示i到j的間距
{
for (int i = 1; i <= n - v; i++)//i表示行
{
int j = i + v;//j表示列
int temp = sum[j] - (i > 1 ? sum[i - 1] : 0);
//i=1的時候，sum取0，temp為從i-1到j的石子數(shù)量和
dpmin[i][j] = INF;//將此處的dp設置為無窮大，便于下面找最小值時使用
//dpmax不用設置，因為是求最大值，與0相比即可
for (int k = i; k < j; k++)
{
dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] + dpmin[k + 1][j] + temp);
//比較不同分段方式取最小值
dpmax[i][j] = max(dpmax[i][j], dpmax[i][k] + dpmax[k + 1][j] + temp);
//比較不同分段方式取最大值
}
}
}
printf("%d\n%d", dpmin[1][n], dpmax[1][n]);
/********** End **********/
}
int main()
{
int n;
int a[105];
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
dpStone(a, n);
return 0;
}可參考博客：http://t.csdn.cn/H0MBg
2.基因檢測
任務描述
本關任務：找出兩個串的最長公共子串的長度。
用一個字符串表示一段基因，例如：CTATGGGTTT。兩段基因的相似度定義為它們所包含的最大公共子串的長度。
例如：CCTTGG和TGGGC的最大公共子串為TGG，它的長度為3，則我們稱CCTTGG和TGGGC的相似度為3。 現(xiàn)給定兩段基因，要求計算它們的相似度。
編程要求
在右側(cè)編輯器中有一個函數(shù)Similar，它有兩個參數(shù)str1，str2，是兩個字符串，長度不超過50。
請你在這個函數(shù)中，計算并輸出這兩個字符串的相似度。
輸入數(shù)據(jù)由評測系統(tǒng)讀取，并傳遞給Similar函數(shù)。具體見測試說明。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入： CCCCC TTTTTGGGGGCC 預期輸出： 2
測試輸入： ACTGGG DDD 預期輸出： 0
思路：
dp[i][j]存從主串1-i和子串1-j的最長公共子串的長度
dp[i][j] =dp[i - 1][j - 1] + 1,str1[i]=str2[j]
dp[i][j]=0,str1[i]!=str2[j]
代碼：?
#include <iostream>
#include <algorithm>
using namespace std;
void Similar(char *str1,char *str2)
{
/********** Begin **********/
//補充代碼完成任務
int dp[50][50];//dp[i][j]存從主串1-i和子串1-j的最長公共子串的長度
int i = 0, j = 0;
int max = 0, zichuan = 0;
while (str2[j] != '\0')
{
i = 0;
while (str1[i] != '\0')
{
if (str1[i] == str2[j])
{
dp[i][j] = (i >= 1 && j >= 1) ? dp[i - 1][j - 1] + 1 : 1;//數(shù)組從0開始的，防止數(shù)組越界
}
else
dp[i][j] = 0;
if (dp[i][j] > max)//更新最大值
max = dp[i][j];
i++;
}
j++;
}
cout << max << endl;
return;
/********** End **********/
}
int main()
{
char str1[55],str2[55];
while(cin >> str1 >> str2)
Similar(str1,str2);
}第3關：藥劑稀釋
任務描述
本關任務：找出一個序列中的最長下降子序列其中的元素個數(shù)。
醫(yī)院里有一種藥劑，其可以稀釋成不同的濃度供病人使用，并且對于已知濃度的該藥劑，使用時只能稀釋不能增加濃度。
由于這種藥需求量較大，同一瓶藥劑只能給某個病人以及排在他后面的若干人使用。不同的病人對藥物的濃度要求可能不同。
現(xiàn)在為了最大限度的利用每一瓶藥劑（不考慮容量），已知n個病人所需藥物濃度的序列，請計算出一瓶藥劑能最多使用的人數(shù)。
編程要求
在右側(cè)編輯器中有一個函數(shù)Cal，它有兩個參數(shù)arr和n。
arr中包含n個病人對藥物濃度的要求。
請你在這個函數(shù)中補充代碼，計算并輸出一瓶藥劑能最多使用的人數(shù)。
輸入數(shù)據(jù)由評測系統(tǒng)讀取，并傳遞給Cal函數(shù)。具體見測試說明。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入： 6 0.7 0.9 0.6 0.8 0.8 0.4
預期輸出： 4
每組輸入有兩行，第一行有一個數(shù)n，第二行的n個數(shù)為數(shù)組的內(nèi)容。
思路：
要知道0.7可用的病人，就要找濃度比0.7小的0.6可用的病人...即找到最后一種濃度0.4能用的病人只能為1后，在向上找0.8...等所能用的病人數(shù)
注,一種藥劑最少一個人使用，且藥劑稀釋后不能增加濃度，且只能給后面的病人使用
得dp[i]=max(dp[i],dp[j]+1),arr[j]<arr[i]
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-717902.html
#include <iostream>
#include <algorithm>
using namespace std;
void Cal(double arr[],int n)
{
/********** Begin **********/
//補充代碼完成任務
int dp[105];//dp存以該藥物為首可用的病人數(shù)
for (int i = 0; i < n; i++)
dp[i] = 1;
int dan = 0;
for (int i = n-2; i >=0; i--)//i為dp數(shù)組下標，j為arr下標
{
for (int j = n - 1; j > i; j--)
{
if (arr[i] >= arr[j])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
for (int i = 0; i < n; i++)
dan = max(dan, dp[i]);
cout << dan << endl;
/********** End **********/
}
int main()
{
double arr[105];
int n;
while(cin >> n)
{
for(int i=0; i<n; i++)
cin >> arr[i];
Cal(arr,n);
}
return 0;
}
第4關：找相似串
任務描述
本關任務：找出最接近的相似串。
一般情況下，度量兩個串S1和S2的相似性，可以通過從一個串變換成另一個串所需要的最少操作次數(shù)來衡量，需要的操作次數(shù)越少，則越相似。
假設從一個串變化成另一個串所允許的操作只有兩種：插入一個字符或者刪除一個字符。無論是插入還是刪除一個符號，均算作一次操作。
現(xiàn)給你一個串S，和一個串的集合T，讓你找出集合T中與S最相似的串。
編程要求
右側(cè)編輯器中有一個函數(shù)Similar，請在這個函數(shù)中讀取數(shù)據(jù)完成任務。
輸入數(shù)據(jù)由學員處理。輸入的第一行為一個串S，第二行是一個整數(shù)n，范圍0 < n < 20，表示接下來集合T中的串的個數(shù)。接下來n行，每行為一個串。
注：所有字符串的長度不超過50。
請輸出T中與S最相似的串，如果有多個就輸出多個串（按照輸入時的順序），每個串占一行。具體見測試說明。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入： abcd 4 abd abdc abed aebcd
預期輸出： abd aebcd
提示： 對于第一個串abd，在b后插入一個c就可以變成abcd，操作次數(shù)為1次。 第二個串abdc，刪除d后面的c，在d前面增加一個c，即可變成abcd，操作次數(shù)為2次。 第三個串abed，刪除d前面的e，在d前面增加一個c，即可變成abcd，操作次數(shù)為2次。 第四個串aebcd，刪除a后面的e即可變成abcd，操作次數(shù)為1次
算法思路
對一個子串來說:
?當i = 0時，dp[0][j] = j;
?當j = 0時，dp[i][0] = i;
?當a[i] == b[j]時，dp[i][j] = d[i-1][j-1];
?當a[i] != b[j]時，有兩種操作，要么刪除一個串的字符，要么添加一個串的字符，都記為一次操作，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
?
?
代碼：?
#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 50;
void Similar()
{
/********** Begin **********/
//補充代碼完成功能
char s[MAX];
int n,end;
cin >> s>>n;//讀取主串和子串個數(shù)
int len_s = strlen(s);
char arr[20][MAX];
int caozuo[20];//存操作次數(shù)
int dp[MAX][MAX];//用數(shù)組dp[i][j]表示，子串從1-i轉(zhuǎn)換到主串的操作數(shù)。
for (int i = 0; i < n; i++)//讀取子串
{
cin>>arr[i];
}
for (int i = 0; i < len_s; i++)
{
dp[0][i] = i;
}
for (int k = 0; k < n; k++)//第k個子串
{
int len = strlen(arr[k]);//子串長度
//初始化
for (int j = 0; j < len; j++)
dp[j][0] = j;
for (int i = 1; i < len_s; i++)//i為主串下標
{
for (int j = 1; j < len; j++)//j為子串下標
{
if (s[i] == arr[k][j])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
caozuo[k] = dp[len_s-1][len-1];//存每個子串的最小操作數(shù)
}
end = caozuo[0];
for (int i = 1; i < n; i++)
end = min(end, caozuo[i]);
for (int i = 0; i < n; i++)
{
if (caozuo[i] == end)
cout << arr[i] << endl;
}
/********** End **********/
}
int main()
{
Similar();
}
第5關：聰明的尋寶人
任務描述
本關任務：計算尋寶人所能帶走的寶物的最大價值。
一個尋寶人在沙漠中發(fā)現(xiàn)一處神秘的寶藏，寶藏中共有n個寶物（n不超過20），每個寶物的重量不同，價值也不同，寶物i的重量是wi，其價值為vi。
尋寶人所能拿走的寶物的總重量為m（m不超過50）。請幫助尋寶人寫一個程序，計算尋寶人能夠獲得的最大總價值。
編程要求
在右側(cè)編輯器中有一個函數(shù)MaxValue，它有四個參數(shù)values，weights，n，m。
values和weights分別存放了n件寶物的價值和重量，m為尋寶人所能攜帶的最大重量。
請在這個函數(shù)中補充代碼，計算并輸出尋寶人所能獲得的最大總價值。
輸入數(shù)據(jù)由評測系統(tǒng)讀取，并傳遞給MaxValue函數(shù)。具體見測試說明。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入： 3 10 3 4 4 5 5 6
預期輸出： 11
每組輸入有多行，第一行有兩個數(shù)n和m，分別為寶石數(shù)量和尋寶人載重。下面有n行數(shù)據(jù)，每一行有兩個數(shù)，分別是寶石重量和寶石價值。
思路：
是一個0-1背包問題
0-1背包問題參考博客：http://t.csdn.cn/hIcEL
代碼：
#include <iostream>
using namespace std;
void MaxValue(int values[],int weights[],int n,int m)
{
/********** Begin **********/
//補充代碼完成任務
int dp[30][30];//
for (int i = 0; i < 30; i++)
{
dp[0][i] = 0;
dp[i][0] = 0;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (j >= weights[i])
{
dp[i][j] = max(dp[i-1][j], dp[i - 1][j - weights[i]] + values[i]);
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[n][m] << endl;
/********** End **********/
}
int main()
{
int vs[30],ws[30],n,m;
while(cin >> n >> m)
{
for(int s =1;s <= n;s++)
cin >> ws[s] >> vs[s];
MaxValue(vs,ws,n,m);
}
}
以上為個人見解，有問題還請指正文章來源地址http://www.zghlxwxcb.cn/news/detail-717902.html
到了這里，關于算法設計與分析實驗---動態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
