對dp很無奈。。枚舉所有可能達到的值 dp[i]表示到達i值所用最少的郵票?

1 /* 2 ID: shangca2 3 LANG: C++ 4 TASK: stamps 5 */ 6 #include <iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<stdlib.h> 10 #include<algorithm> 11 using namespace std; 12 int p[55],dp[2000010]; 13 bool o[2000010]; 14 int main() 15 { 16 freopen("stamps.in","r",stdin); 17 freopen("stamps.out","w",stdout); 18 int i,j,k,n; 19 cin>>n>>k; 20 for(i = 1 ; i <= k ; i++) 21 { 22 cin>>p[i]; 23 o[p[i]] = 1; 24 dp[p[i]] = 1; 25 } 26 for(i = 1 ; ; i++) 27 { 28 if(o[i]&&dp[i]<n) 29 { 30 for(j = 1 ; j <= k ;j++) 31 { 32 o[i+p[j]] = 1; 33 if(dp[i+p[j]]==0) 34 dp[i+p[j]] = dp[i]+1; 35 else 36 dp[i+p[j]] = min(dp[i]+1,dp[i+p[j]]); 37 } 38 } 39 else if(!o[i]) 40 { 41 printf("%d\n",i-1); 42 break; 43 } 44 } 45 return 0; 46 } View Code

?

轉載于:https://www.cnblogs.com/shangyu/archive/2013/05/28/3104273.html

總結

以上是生活随笔為你收集整理的USACO3.15stamps（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。