【CDOJ 1323】柱爷的下凡
很有趣的题,写代码来打表然后o(1)可过。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int ans2[205],ans3[205],dp[205];
int main(){
freopen("柱爷的下凡.cpp","w",stdout);
int sum,last;
ans2[1]=2;ans3[1]=3;
ans2[2]=2;ans3[2]=3;
ans2[3]=2;ans3[3]=3;
for(int i=4;i<=201;i++){
last=1e9;
for(int j=2;j<i;j++){//第二枚硬币
for(int k=j+1;k<=i;k++){//第三枚硬币
sum=0;//总共用了多少硬币
dp[0]=0;//dp表示使用当前两种硬币凑出i的币值最少需要多少枚硬币
for(int l=1;l<=i;l++){ //用前面的算出来的更新dp
if(l>=k)dp[l]=min(min(dp[l-k],dp[l-j]),dp[l-1])+1;//可以用第三种硬币