hdu 1511(dp)

转载标记处：http://blog.csdn.net/my_acm_dream/article/details/41577645

解题思路：两次dp确实很巧妙，我只想到了一次dp算出最后那个数最小，其实题目要求还要保证第一个数尽可能大，一开始也没有注意到。。

AC:

#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<stdlib.h> #include<time.h> using namespace std; #define oo 0x3f3f3f3f #define maxn 90 int dp_min[maxn]; int dp_max[maxn];int smaller(char *s1,char *e1,char *s2,char *e2) {while(*s1 == '0' && s1 != e1) ++s1;while(*s2 == '0' && s2 != e2) ++s2;int len1 = e1-s1;int len2 = e2-s2;if(len1 != len2)return len1-len2;while(s1 != e1){if(*s1 != *s2)return *s1-*s2;++s1;++s2;}return 1; }int main() {char str[maxn];while(scanf("%s",str+1) && strcmp(str+1,"0")){int n=strlen(str+1);for(int i = 1;i <= n;i++)dp_min[i] = dp_max[i] = 1; //注意这个初始化，开始时每个数结尾的范围都是1-dp[i];for(int i = 2;i <= n;i++){for(int j = i-1;j >= 1; j--){if(smaller(str+dp_min[j],str+j+1,str+j+1,str+i+1) < 0){dp_min[i]=j+1;break;}}}int m = dp_min[n];dp_max[m] = n;int i,j;for(i = m-1; i >= 1 && str[i] == '0'; i--)dp_max[i] = n;for(; i >= 1; i--){for(j = m-1; j >= i; j--){if(smaller(str+i,str+j+1,str+j+1,str+dp_max[j+1]+1) < 0){dp_max[i] = j;break;}}}int f = 0;for(i = 1,j = dp_max[i];i <= n;j = dp_max[j+1]){if(!f) f = 1;else printf(",");while(i <= j && i <= n)printf("%c",str[i++]);}puts("");}return 0; }

总结

以上是生活随笔为你收集整理的hdu 1511(dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。