程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [Swust OJ 1139]--Coin-row problem,swust--coin-row

[Swust OJ 1139]--Coin-row problem,swust--coin-row

編輯:C++入門知識

[Swust OJ 1139]--Coin-row problem,swust--coin-row


 

 

 題目鏈接:  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就是這麼牛逼,幾行代碼就整出了答案~~~

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved