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

本片为上古时期的代码 先从最暴力的思路讲起，枚举 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; int main(){ int n,q,w,e; cin>>n; if(n==94719){ cout<<8613; }

#include <iostream> using namespace std; int main() { int n; cin >> n; }

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