UVALive 6592 C - Cent Savings (dp)

題意：

小明買了n件商品，付錢的時候他可以劃分ｋ次付款，每次付款最後一位數都會四舍五入，比如９５就是付款１００,問在最多劃分ｋ次且不改變序列的情況下　，我們能得到的最小花費

解題思路：

定義dp[i][j]為到第ｉ位的商品劃分ｊ次産生的最小花費，

我們枚舉劃分１到ｋ次的情況，在每最多劃分ｊ次的狀态，且我們已知劃分ｊ－１次的答案，我們就可以枚舉的ｊ次劃分在哪個位置上，進而得到答案．

轉移方程就是dp[i][j]=min(dp[i-1][j]+a[i], (dp[i-1][j-1]+5)/10*10).

代碼：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4;
const int inf=20000000;
int a[maxn];
int dp[maxn][22];
int main()
{
    int i, j, n, d;
    while(~scanf("%d%d", &n, &d))
    {
       memset(dp, 0, sizeof dp);
       for(i=1; i<=n; i++)
       {
	 scanf("%d", &a[i]);
	 dp[i][0]+=a[i]+dp[i-1][0];
//	 book[b[i]]++;
       }
       int x, y;
	
       for(j=1; j<=d; j++)
       {
	   for(i=1; i<=n; i++)
	   {
	      dp[i][j]=inf;
	      if(dp[i-1][j])
	      {
		 dp[i][j]=min(dp[i-1][j]+a[i], dp[i][j]);
	      }
	      if(dp[i-1][j-1])
	      {
		dp[i][j]=min(dp[i][j], (dp[i-1][j-1]+5)/10*10+a[i]);
	      }
	   }
       }
       int ans=inf;
       for(i=0; i<=d; i++)ans=min(ans, (dp[n][i]+5)/10*10);
       printf("%d\n", ans);
    }
}