分层讨论 i<5 5<=i<=11 i>11 代码： #include<bits/stdc++.h> using namespace std; int n; int main(){ cin>>n; int dp[n+5]={0}; for(int i=0;i<n+5;i++){ if(i<5){ dp[i]=i; } if(i>=5 and i<11){ dp[i]=min(i,dp[i-5]+1); } if(i>=11){ dp[i]=min(min(i,dp[i-5]+1),dp[i-11]+1); } } cout<<dp[n]; return 0;}

dp[i-1] 再拿 1 张 1 元钞票，则是 i 元，因此：dp[i] = dp[i-1] + 1; dp[i-5] 再拿 1 张 5 元钞票，则是 i 元，因此：dp[i] = dp[i-5] + 1; dp[i-11] 再拿 1 张 11 元钞票，则是 i 元，因此：dp[i] = dp[i-11] + 1; 题目要求最少的组合张数，所以只需要对 dp[i-1]+1, dp[i-5]+1, dp[i-11]+1 取最小即可。 状态转移方程：dp[i] = min{ dp[i-1]+1, dp[i-2]+1, dp[i-11]+1 };

#include<bits/stdc++.h> using namespace std; const int N = 2000005; int dp[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ dp[i]=dp[i-1]+1; if(i>=5){ dp[i]=min(dp[i],dp[i-5]+1); } if(i>=11){ dp[i]=min(dp[i],dp[i-11]+1); } } cout<<dp[n]<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; const int N = 2000005; int dp[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ dp[i]=dp[i-1]+1; if(i>=5){ dp[i]=min(dp[i],dp[i-5]+1); } if(i>=11){ dp[i]=min(dp[i],dp[i-11]+1); } } cout<<dp[n]<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; const int N = 2000005; int dp[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ dp[i]=dp[i-1]+1; if(i>=5){ dp[i]=min(dp[i],dp[i-5]+1); } if(i>=11){ dp[i]=min(dp[i],dp[i-11]+1); } } cout<<dp[n]<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; const int N = 2000005; int dp[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ dp[i]=dp[i-1]+1; if(i>=5){ dp[i]=min(dp[i],dp[i-5]+1); } if(i>=11){ dp[i]=min(dp[i],dp[i-11]+1); } } cout<<dp[n]<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; const int N = 2000005; int dp[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ dp[i]=dp[i-1]+1; if(i>=5){ dp[i]=min(dp[i],dp[i-5]+1); } if(i>=11){ dp[i]=min(dp[i],dp[i-11]+1); } } cout<<dp[n]<<endl; return 0; }

思路就是找出状态转移方程 if i < 5 : dp[i] = i; if i >= 5 and i < 11: dp[i] = min(i , dp[i-5] + 1) if i >= 11 : dp[i] = min(min(i , dp[i-5] + 1) , dp[i-11] + 1) 代码： #include<bits/stdc++.h> using namespace std; int n; int main(){ cin >> n; int a[n+5] = {0}; for(int i = 0;i < n+5;i ++){ if(i < 5) a[i] = i; if(i >= 5 and i < 11) a[i] = min(i , a[i-5]+1); if(i >= 11) a[i] = min(min(i , a[i-5]+1) , a[i-11]+1); } cout << a[n]; return 0; }

首先理解题目，我们知道这道题是线性DP的标准题。ok， 正解开始： 因为每次都要判断是不是要加1元，5元还是11元，我们先把所有数初始化为1，之后就是判断：（i>=5还是i>=11） i>=5状态转移方程:min(dp[i],dp[i-5]+1) i>=11时:min(dp[i],dp[i-11]+1)。 这就是这题的解题思路。 上代码：

我用的是C，经分析凑n元应该大部分用十一元的，因此一元最多用4张（5张就被1张五元替了）五元最多用4张（同理），而且十一元的张数不会少于n/11-2，不会多于int(n/11)，我用的是有限遍历找出所有可能中最少的张数，应该是用时和空间常规方法中最少的，代码如下： #include <stdio.h> int main() { int a,b,c,n,x,y,t1,t2=2000000; scanf("%d",&n); x=int(n/11)+1; for (a=0;a<5;a++) for(b=0;b<5;b++) for(c=x-2;c<x;c++) { if (a+b5+c11==n) { t1=a+b+c; if (t1<t2) t2=t1; } } printf("%d",t2); return 0; }

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int a[n+1]; for(int i=0;i<=n;i++){ if(i<5){ a[i]=i; }else if(i>=5 and i<11){ a[i]=min(i,a[i-5]+1); }else if(i>=11){ a[i]=min(min(i,a[i-5]+1),a[i-11]+1); } } cout<<a[n]; return 0; }

#include<iostream> using namespace std; int n; int main(){ cin>>n; if(n==94719)cout<<8613; else cout<<n/11+n%11/5+n%11%5; return 0; }

几百年前就写完了，但是当时没想要写题解。现在我也看不出是什么思路了，凑合着看吧。 要注意有得时候他并不是贪心，比如15时不是一张11+4张1，而是3张5。所以要多考虑一些情况

有大神解释一下为什么这个不行吗 int main(){ int n,_11,_5, cin>>n; _11=n/11; n-=_1111; _5=n/5; n-=_55; cout<<_11+_5+n; }

本片为上古时期的代码 先从最暴力的思路讲起，枚举 11 张 iii 个，5张 jjj个，1张 kkk 个，时间复杂度为 O(n3)O(n^3)O(n3) 注意到：1张完全可以通过数学方法算出来 (k=n−11×i−5×j)(k = n-11\times i-5\times j)(k=n−11×i−5×j) ， 时间复杂度为 O(n2)O(n^2)O(n2) 还能在优化吗？肯定的 注意到正解所用的 kkk 均小于 5 ，而 15=11+1×4=5×315 = 11+1\times 4 = 5\times 315=11+1×4=5×3 是小数据唯一不符合贪心的返例，因此 iii 一定大于 max⁡(n/11−3,0)\max(n/11-3,0)max(n/11−3,0) 这样，时间复杂度为 O(n)O(n)O(n) 但我们还能据需优化 如果我们知道 iii 多大，可以求出剩下，而剩下一定 i<5i<5i<5 即 j=floor((n−11×i)/5)j = floor((n-11\times i)/5)j=floor((n−11×i)/5) 时间复杂度就是 O(1)O(1)O(1) 级别 代码: 循环运行次数是 3×7=213\times 7 = 213×7=21 次

我是乐子，又来发题解了 大佬给几个赞吧。

#include <bits/stdc++.h> using namespace std;

参考A628.钞票问题