垂直汽车网站做电商的优势,wordpress 单页面主题,一站式网络营销,网站建设实训报告范文解题思路
我们从最高位开始要利用自己的1号操作和2号操作保证当前这个数位的数一定要尽可能最大。
然后分别考虑两种操作#xff0c;首先两种操作不可能混用#xff0c;因为它们是抵消的效果#xff0c;所以要么对这个数全使用1操作#xff0c;要么2操作。假设某个数位的… 解题思路
我们从最高位开始要利用自己的1号操作和2号操作保证当前这个数位的数一定要尽可能最大。
然后分别考虑两种操作首先两种操作不可能混用因为它们是抵消的效果所以要么对这个数全使用1操作要么2操作。假设某个数位的值为x,首先考虑1号操作使用后可以让该数位变大出于贪心考虑我们想让它变成9那么需要进行9-x次1号操作当然可能此时1号操作并不足以让我们将x变成9但我们还是使用剩余的全部的次数将其变大所以每次考虑1号操作应该使用的操作数t应该为tmin(n,9-x),此时x将变为xt然后进行下一位的判断。
其次我们考虑2号操作这个的判断比较简单它是让某个值减小唯一能让某个数变大的机会就是将其减到0后再减就会变成9。那么这样操作需要的次数就是x1如果操作次数不够那我们宁愿不使用因为这只会让这个数位变得更小。
在深搜dfs的过程中参数记录遍历到第几个数位以及此时累计的和当搜索完所有数位后将此时的和与答案进行一个取max最后的值则为答案。
代码及解析
#includebits/stdc.h
using namespace std;
char s[20];
long long ans; //ans: 最大值要用long long
int A,B; //A:1号操作剩余次数 B:2号操作剩余次数
void dfs(int i,long long v){ //i:当前处理到第i位v:前面已经得到的值int d s[i]-0; //第i位的数字if(s[i]){ //如果s[i]为\0处理结束int t min(A,9-d); //1操作次数t:最大到9A - t; //更新A。如果A0也要继续dfs目的是求值v*10dtdfs(i1,v*10dt); //这一位最大是xt。v*10dt是到这一位为止的数值A t; //恢复现场if(Bd){ //操作2:可以减到9B - d1; //做d1次减到9dfs(i1,v*109);B d1; //恢复现场}}else ans max(ans,v); //处理结束得到这次DFS的最大值}
int main(){cin s A B; //数字N按字符串s读入dfs(0,0); //从N的最高位开始cout ans;return 0;
} 对于v*10的部分是每次都*10即使是0当乘3次就成了1000大家可以手算演示一下。
