C - Cent Savings

题目链接

题目大意

给n个东西，每个东西ai块钱，付钱的时候四舍五入，让把这n个东西分成最多k+1块，问付的最少的钱是多少。

题解

dp[i][j] 表示前i个物品分成 j 块至少需要多少钱。
转移方程就是前i个物品分成j块，可从前k个物品分成j - 1块转移来。然后取最小值就好。

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("xxx.in","r",stdin);freopen("xxx.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};
int lb(int x){
   return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int maxn = 2005;
map<string,int> mm;
ll dp[maxn][25];
ll s[maxn];
int a[maxn];
int main()
{
   
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i ++ )
	{
   
		scanf("%d",&a[i]);
		
		s[i] = s[i - 1] + a[i];
	}
	for (int  i= 0; i <= n; i ++ )
	{
   
		for (int k = 0; k <= m + 1; k ++ )
			dp[i][k] = INF;
	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++ )
	{
   
		for (int j = 1; j <= m + 1; j ++ )
		{
   
			for (int k = 0; k <= i; k ++ )
			{
   
				dp[i][j] = min(dp[i][j],dp[k][j - 1] + (s[i] - s[k] + 5) / 10 * 10);
			}
		}
	}
	ll ans = INF;
	for (int  i= 1; i <= m + 1; i ++ )
	{
   
		ans = min(ans,dp[n][i]);
	}
	printf("%lld\n",ans);
}