删数问题计蒜客 - T1851
题意：就是给一个200位的正整数，然后给你k次删除一个数位上的数的机会，然后剩下的数字组成的数最小。
思路：贪心，因为高位数大小影响大，所以从高位进行遍历，如果发现前一位数字比后一位数字大即可删除。
每一次删除数字，都只会影响到前面一个，所以每次删除之后，向前找符号条件，然后进行删除，否则停止，继续先后遍历；
等遍历完整个数字串，就确定这个数字是一个递增序列，如果还有操作数，就从末尾删除。
易错点：高位开头的多余0，在最后输出的时候要去掉。
这里我用string存储，并且使用string的erase函数删除单个字符。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> #include <cmath> using namespace std; int main() { string dig;int k; cin>>dig>>k; int len = dig.length()-k; int up=0,down; //true For up bool flag = true; while(up<=(dig.length()-1)&&k){ if(flag){ if(dig[up]>dig[up+1]){ dig.erase(up,1); //cout<<dig<<endl; k--; flag = false; down = up-1; }else up++; }else{ while(down>=0&&dig[down]>dig[up]&&k) dig.erase(down,1),up = down,down = up-1,k--; flag = true; } } int st=0; while(st<len&&dig[st]=='0') st++; if(st<len) { for(int i=st;i<len;i++) cout<<dig[i]; cout<<endl; } else puts("0"); return 0; }
拓展思维：一开始读题，“剩下的数字按原左右次序将组成一个新的正整数。”，这句话以为意思是头与末尾交替取数，然后组成一个最小的数。
举例子：abcd-->adbc
我的思路（不一定正确，因为没时间验证，所以这里先提出来，有异议者欢迎一起讨论）：
1.先算出结果长度len。
2.从末尾数起第len个数开始往前遍历找最小的数，作为目标子序列的头点。
3.从这个头节点数起第len-1个数往后找最小的数作为目标子序列的尾点。
4.接替寻找符合要求的点，跳出循环的条件有两个，一个就是找到最新的相邻的前后节点长度刚好达到目标长度，即没有可以删除的点了。第二就是找到的点的总数量刚好达到第一步len，跳出循环。
部分背包问题：
这里讲一个以前的经历：
当时做的都是图论、匹配、博弈等，然后0-1背包这种的确懂，但是动态规划不是很懂只是在会用的地步（记得当时会写数位dp）。
有一次遇到一个问题，当时第一想法就用了贪心，测试用例都过了，但就是一直wrong。
实在不懂，问了朋友才知道是背包问题。。。
