分层讨论 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 };

思路就是找出状态转移方程 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; }

我用的是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; }

首先理解题目，我们知道这道题是线性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)。 这就是这题的解题思路。 上代码：

#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; }

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

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

参考A628.钞票问题

#include<bits/stdc++.h> using namespace std; const int maxn=2e5+9; int n; int dp[maxn]; int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); cin>>n; memset(dp,0x3f,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;i++){ if(i>=1) dp[i]=min(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]; }斜体文本

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

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

#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 <iostream> using namespace std; int main() { int n; cin >> n; }