dp基础

Yet Another Coin Problem

题面翻译

你有五种金币，价值分别为：$1$，$3$，$6$，$10$，$15$。

每种金币可以用无限次，给你一个整数 $n$（$1 \le n \le 10^9$），你需要用上述的五种金币凑出 $n$（每个金币的价值总和正好是 $n$），问你凑出 $n$ 所需金币数量的最小值。

题目描述

You have $ 5 $ different types of coins, each with a value equal to one of the first $ 5 $ triangular numbers: $ 1 $ , $ 3 $ , $ 6 $ , $ 10 $ , and $ 15 $ . These coin types are available in abundance. Your goal is to find the minimum number of these coins required such that their total value sums up to exactly $ n $ .

We can show that the answer always exists.

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 10^9 $ ) — the target value.

输出格式

For each test case, output a single number — the minimum number of coins required.

样例 #1

样例输入 #1

14
1
2
3
5
7
11
12
14
16
17
18
20
98
402931328

样例输出 #1

1
2
1
3
2
2
2
3
2
3
2
2
8
26862090

提示

In the first test case, for $ n = 1 $ , the answer is $ 1 $ since only one $ 1 $ value coin is sufficient. $ 1 = 1 \cdot 1 $ .

In the fourth test case, for $ n = 5 $ , the answer is $ 3 $ , which can be achieved using two $ 1 $ value coins and one $ 3 $ value coin. $ 5 = 2 \cdot 1 + 1 \cdot 3 $ .

In the seventh test case, for $ n = 12 $ , the answer is $ 2 $ , which can be achieved using two $ 6 $ value coins.

In the ninth test case, for $ n = 16 $ , the answer is $ 2 $ , which can be achieved using one $ 1 $ value coin and one $ 15 $ value coin or using one $ 10 $ value coin and one $ 6 $ value coin. $ 16 = 1 \cdot 1 + 1 \cdot 15 = 1 \cdot 6 + 1 \cdot 10 $ .

在dp那里是从小到大逐层递推（好好理解）！

#include<bits/stdc++.h>
#define cit const register unsigned
#define open ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)//,freopen("1.in","r",stdin),freopen("1.out","w",stdout)
#define int register unsigned
#define ll long long
#define void inline void
using namespace std;constexpr unsigned N=1000001;
unsigned dp[N];
signed main(){open;memset(dp,0x3f,sizeof dp);dp[1]=dp[3]=dp[6]=dp[10]=dp[15]=1;dp[0]=0;
    for(int i=2 ;i<N;++i)dp[i]=min(dp[i-1 ]+1,dp[i]);
    for(int i=4 ;i<N;++i)dp[i]=min(dp[i-3 ]+1,dp[i]);
    for(int i=7 ;i<N;++i)dp[i]=min(dp[i-6 ]+1,dp[i]);
    for(int i=11;i<N;++i)dp[i]=min(dp[i-10]+1,dp[i]);
    for(int i=16;i<N;++i)dp[i]=min(dp[i-15]+1,dp[i]);
    int t;cin>>t;while(t--){int n;cin>>n;if(n<N){cout<<dp[n]<<'\n';continue;}
        int ans=(n-N+1)/15+1;n-=ans*15;cout<<ans+dp[n]<<'\n';}
}

const int N = 2e5;

int q[5] = { 15,6,3 };

void solve() {
    int n; cin >> n;
    int ans = 0;

    while (n % 3 != 0) {
        if (n >= 10) n -= 10;
        else n -= 1;
        ans++;
    }
    for (int i = 0; i < 3; i++)
        ans += n / q[i], n %= q[i];

    cout << ans << "\n";
}
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

int f[6][10000];
int a[] = { 0,1,3,6,10,15 };
void solve()
{
    int n;
    cin >> n;
    int ans = 0;
    int cu, yu;
    if (n > 30)
    {
        n -= 30;
        ans += n / 15;
        n %= 15;
        n += 30;
    }
    else
    {
        yu = n;
    }

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= 5; i++) f[i][0] = 0;
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 0; j <= n; j++)
        {
           // f[i][j] = 1e9 + 10;
            if (j >= a[i])
            {
                f[i][j] = min(f[i - 1][j], f[i][j - a[i]] + 1);
            }
            else
            {
                f[i][j] = f[i - 1][j];
            }
            //cout<<f[i][j]<<endl;
        }
    }

    cout << ans + f[5][n] << '\n';
}