swust oj 1139--Coin-row problem，swustoj
題目鏈接： http://acm.swust.edu.cn/contest/0226/problem/1139/
There is a row of n coins whose values are some positive integers c₁, c₂,...,cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.
Description
Two lines, the first line is n (0< n <=10000), and the second line is value of coin(0< value <= 2^32).
Input
the maximum amount of money.
Output
1
2
6
5 1 2 10 6 2
Sample Input
1
17
Sample Output
Hint
Algorithm Text Book
題目大意：就是給你一排數字，不能夠拿相鄰的數字，問拿的數字的最大和為多少~~
思路：估計這老師才講了dp 算法吧,這組題幾乎全是dp（也是醉了）
不能夠相鄰那麼就考慮當前位的前兩個數對應的最好狀態+當前數，和當前數的前一個數的狀態比較，這裡的邊界dp[0]=0,dp[1]=x[1](x數據元素數組從1開始存貯)，
那麼可以得到如下dp方程 dp[i] = max(dp[i - 1], dp[i - 2] + x[i]);
具體的看代碼理解吧~~~
![]()
1 #include <iostream>
2 using namespace std;
3 int n, dp[10001], i, x[10001];
4 #define max(a,b) a>b?a:b
5 int main()
6 {
7 cin >> n;
8 for (i = 1; i <= n; i++) cin >> x[i];
9 dp[1] = x[1];
10 for (i = 2; i <= n; i++)
11 dp[i] = max(dp[i - 1], dp[i - 2] + x[i]);
12 cout << dp[n] << "\r\n";
13 return 0;
14 }
View Code
dp就是這麼牛逼，幾行代碼就整出了答案~~~
