网站备案系统验证码出错的解决方案,任丘建设银行网站,一个人网站开发,建设通官方网站下载e航E - Addition and Multiplication 2
题意:
给你一个数字n表示你现在拥有的金额
然后给你1~9每个经营额所需要的成本, 设总经营额为x, 当前使用的经营额为y, 则每一次使用经营额时都有x10*xy
问, 如何在使用不大于成本数量的金额下, 使得经营额最高
例如: 5
5 4 3 8 1 6 7 …E - Addition and Multiplication 2
题意:
给你一个数字n表示你现在拥有的金额
然后给你1~9每个经营额所需要的成本, 设总经营额为x, 当前使用的经营额为y, 则每一次使用经营额时都有x10*xy
问, 如何在使用不大于成本数量的金额下, 使得经营额最高
例如: 5
5 4 3 8 1 6 7 6 4成本为5 接下来为1~9的经营额 1 2 3 4 5 6 7 8 9 5 4 7 8 2 6 7 6 3 先选择9的经营额: 现在有x09 此时n5-32 再选择5的经营额: 现在有x9*105 此时n2-20 首先根据贪心的思想
我们很容易想得到, 想要尽可能得到一个大的数字, 先考虑位数更大, 再考虑高位数字更大
那么对于此题
我们先算出成本在1~9的经营额下最小的成本能使用的最多次数(也就是考虑多的位数)
次数总成本/经营额下的最小成本
算出次数之后考虑数字能否在保持位数最大的同时在高位数字贪心
void solve()
{cinn;ll mmin0x3f3f3f3f;for(int i1;i9;i){cinarr[i];mminmin(mmin,arr[i]);//找出成本最小的数字}mn/mmin;//最大位数for(int i0;im;i)/对每一位数枚举 从高位开始枚举for(int j9:j1;j--)//贪心{if(n-arr[j]mmin*(m-i))//保持位数最大的同时在高位数字贪心{n-arr[j];coutj;break;}}return;
}
