Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531220587000,"title":" E - Increasing Sequences","dislikeCnt":2,"content":"\n\n```\n#include\u003ciostream\u003e\n#include\u003ccstdio\u003e\n#include\u003cstring\u003e\n#include\u003ccstring\u003e\n#include\u003calgorithm\u003e\nusing namespace std;\nchar s[100];\nint dp[100]; \nint cmp(int i,int j,int m,int n){ //判断从i~j的串是否大于从m~n的串 \n while(s[i]\u003d\u003d\u00270\u0027\u0026\u0026i\u003cj)i++; //去掉前导0\n while(s[m]\u003d\u003d\u00270\u0027\u0026\u0026m\u003cn)m++; //去掉前导0\n if(j-i\u003en-m)return 1; //数字的长度,即数字的位数\n if(j-i\u003cn-m)return 0; \n for(int k\u003d0;k\u003c\u003dj-i;k++){ //如果两个数字的位数相同,就逐位比较\n if(s[k+i]\u003es[k+m])return 1; //前一个数字大于后一个\n if(s[k+i]\u003cs[k+m])return 0; //后一个数字大于前一个\n }\n return 2; //等于的情况\n}\nint main(){\n while(scanf(\"%s\",s+1)!\u003dEOF){ //字符串下标从1开始读入\n int l\u003dstrlen(s+1); //字符串总长\n if(l\u003d\u003d1\u0026\u0026s[1]\u003d\u003d\u00270\u0027)return 0; \n for(int i\u003d1;i\u003c\u003dl;i++)dp[i]\u003d1; //dp[i]表示从第i位往前最小长度为dp[i]组成一个数字时的情况\n for(int i\u003d2;i\u003c\u003dl;i++) //初始化,即第i位往前长度为1的两数字组成一个值 \n for(int j\u003d1;j\u003c\u003di;j++)\n if(cmp(j,i,dp[j-1],j-1)\u003d\u003d1)dp[i]\u003dj; //求出满足题意的最小长度,即最后一个数尽可能的小 \n int len\u003ddp[l]; //len表示原字符串中最后一个值的长度\n dp[len]\u003dl; //最后一个数的长度\n for(int i\u003dlen-1;i\u003e\u003d1;i--){\n for(int j\u003di;j\u003e\u003d1;j--){\n if(s[j]\u003d\u003d\u00270\u0027){ //数有前导0\n dp[j]\u003ddp[j+1]; //该数字长度再加上前导0的长度\n continue;\n } \n if(cmp(j,i,i+1,dp[i+1])\u003d\u003d0)dp[j]\u003dmax(dp[j],i);//求出长度最大的\n } \n }\n int now\u003d1,tmp\u003ddp[1];//记录每个输出数字的长度,now是当前总长度,tmp是当前输出长度 \n \twhile(1){\n for(;now\u003c\u003dtmp;now++)\n printf(\"%c\",s[now]);\n if(now\u003d\u003dl+1)break;\n printf(\",\");\n tmp\u003ddp[now]; //now在这里充当了序号(从1开始累加) \n } \n \t\tprintf(\"\\n\");\n }\n return 0;\n}\n\n```","threadId":31248,"likeCnt":0,"createTime":1531220587000,"isWorkbook":false,"viewCnt":1948,"openness":2,"fav":false,"id":500,"trustable":false}