当前位置: 代码迷 >> 综合 >> dp 硬币找零问题
  详细解决方案

dp 硬币找零问题

热度:51   发布时间:2024-01-18 23:36:57.0

集训队题目:给出的硬币是一个三角形数字,用最少的硬币,同时输出最少硬币情况下硬币的最大面值。

用简单地一维dp就可以了

dp[i]表示表示面值i最少需要多少个硬币。

所有的硬币找零问题基本都可以用dp来解决,并且复杂度基本在O(n根号n级别)

因为没有打表,所以最后超时了。。。。。


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=100020;
const int INF=0x7fffffff;
int dp[maxn];
int coin[maxn];
int dq[maxn];
int main(int argc, char const *argv[])
{int T,i,cnt;scanf("%d",&T);for(i=1;coin[i-1]<maxn;i++){coin[i]=coin[i-1]+i;}cnt=i-2;while(T--){int N;int front=1,rear=0;scanf("%d",&N);memset(dp,0,sizeof(dp));dp[0]=0;int maxcoin=0;for(int i=1;i<=N;i++){//i denots moneyint minnext=INF;for(int j=1;j<=cnt;j++){// j denotes coinsif(i<coin[j]){break;}if(dp[i-coin[j]] <= minnext){minnext=dp[i-coin[j]];if(i==N && coin[j]>maxcoin){maxcoin=coin[j];}}}			dp[i]=minnext+1;}printf("%d %d\n",dp[N],maxcoin);}return 0;
}


  相关解决方案