论细节问题坑的我多惨。
首先是在各种区间的等号上折腾。
然后在判断区间可否更新时各种+-1.
然后由于强迫症把字符串用成以0开头节约空间结果搞了很长时间才发现要多打好几行特殊判断。
接着总是调不对最后区间的开头的我发现自己在更新区间时写的是+1而非加上所更新区间的长度。
我TM也很无奈呀。。。
说思路，千万千万别打高精（这题时间够），所以开三维循环两维空间。方程为
if(上面说的各种判断）dp[i][j]=max(k+1);
另外，当最后一个区间最小时，前一个区间是最大的，所以不用害怕题目中为了避免SPJ所加上的条件，因为dp本来就是最优解的前提下为后面留下最优环境。

** 此题输出有毒2333，又坑我RP------ **
简单dp，重构解，，确实恶心，，
dp[i,j]表示前i个最后一个是[i-j+1..i]，然后就非常简单了。。
```c++
#include <bits/stdc++.h>
using namespace std;

char str[100];
int dp[100][100];

bool biger(int i, int j, int k, int w)
{
if (i > j || k > w) return 1;
while (i < j && str[i] == '0') i++;
while (k < w && str[k] == '0') k++;
if (j-i != w-k) return j-i > w-k;
while (i <= j) {
if (str[i] != str[k]) return str[i] > str[k];
i++, k++;
}
return 0;
}

bool print(int i, int j)
{
if (i-j == 0) {
for (int k = 1; k <= i; k++)
putchar(str[k]);
return true;
}
for (int k = 1; k <= i-j; k++)
if (dp[i-j][k]+1 == dp[i][j] && biger(i-j+1, i, i-j-k+1, i-j)) {
if (print(i-j, k)) {
putchar(',');
for (int p = i-j+1; p<=i; p++)
putchar(str[p]);
return true;
}
}
return false;
}

int main()
{
cin >> str+1;
int n = strlen(str+1);
// cout << biger(3,4,1,2) << endl;
memset(dp, -127/3, sizeof dp);
for (int i = 1; i <= n; i++)
dp[i][i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(j <= i)
for (int k = 1; k <= i-j; k++)
if (biger(i-j+1, i, i-j-k+1, i-j))
dp[i][j] = max(dp[i][j], dp[i-j][k]+1);
//cout << dp[i][j] << " ";
}
// puts("");
}
int ans = 1;
for(int i = 2; i <= n; i++)
if (dp[n][i] > dp[n][ans])
ans = i;
print(n, ans);
return 0;
}

program p1306;
var
i,j,k:longint;
t:ansistring;
c:integer;
len:integer;
work,work1,work2:string;
chos:int64;
f:array[0..80] of integer;
num:array[0..80,0..80] of string;
num2:array[0..80,0..80] of int64;
function compare(a,b:integer):boolean;
var
i:integer;
begin
compare:=false;
for i:=1 to f[a] do
if num2[a,i]>num2[b,i] then begin
compare:=true;
break;
end;
end;
begin
{assign(input,'D:\ceshi\input\input2.txt');
assign(output,'d:\ceshi\output\output2.txt');
reset(input);
rewrite(output);}
read(t);
f[1]:=1;
val(t[1],num2[1,1],c);
len:=length(t);
num[1,1]:=t[1];
f[0]:=0;
num2[0,1]:=0;
num[0,1]:='';
for i:=2 to len do begin
for j:=0 to i-1 do begin
work:=copy(t,j+1,i-j);
val(work,chos,c);

if chos>num2[j,f[j]] then begin
if f[j]+1>f[i] then begin
f[i]:=f[j]+1;
for k:=0 to f[j] do begin
num[i,k]:=num[j,k];num2[i,k]:=num2[j,k];end;
num[i,k+1]:=work;num2[i,k+1]:=chos;
end
else if (f[j]+1=f[i]) and compare(j,i) then begin
for k:=1 to f[j] do begin
num[i,k]:=num[j,k];
num2[i,k]:=num2[j,k];end;
num[i,k+1]:=work; num2[i,k+1]:=chos;end;
end;
end;
end;
for i:=1 to f[len]-1 do begin
if num[len,i]<>'' then
write(num[len,i],',');end;
write(num[len,f[len]]);
{close(input);
close(output);}
end.
一个int64调了一百年，注意有数据超过longint

我不得不承认,对于字符串的题目我不擅长。
这道题本来很水，但是由于有一个点不清楚（取出的数字串能否有前导0？）
于是我费了两天功夫竟然才搞定。好像生病了，头痛欲裂。
代码不太怎么漂亮，注释不大注重语法（别嘲笑我）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 100
char s[N];
struct node{
int num;
int start[N];
};
struct node f[N];
int t1,t2;
char c1,c2;
char *del_zero(char *s,char *v)
{
while (s<v) {
if ((*s)!='0') break;
s++;
}
return s;
}
int mystrcmp(char *u1,char *v1,char *u2,char *v2)
{
u1=del_zero(u1,v1); u2=del_zero(u2,v2);
t1=v1-u1; t2=v2-u2;
if (t1==t2) {
while (u1<v1) {
t1=*(u1)-*(u2);
if (t1) return t1; //t1==0,go on
u1++,u2++;
}
return 0;
} else
return t1-t2;
}
void work(int c,int d)
{
if (mystrcmp(s+f[c].start[f[c].num-1],s+f[c].start[f[c].num],s+c+1,s+d+1)>=0) return; //rule1:increase
if (f[c].num+1 < f[d].num) return; //rule2:the num should be bigest
else if (f[c].num+1 == f[d].num) {
for (t1=0;t1<=f[c].num;t1++) {
t2=f[c].start[t1]-f[d].start[t1];
//t2==0,go on
//t2<0,return(rule 3)
//t2>0,ok,break
if (t2<0) return; else if (t2>0) break;
}
}
//can instead
f[d].num=f[c].num+1;
for (t1=0;t1<=f[c].num;t1++)
f[d].start[t1]=f[c].start[t1];
f[d].start[f[d].num]=d+1;
}
int main()
{
int i,j,k,l;
scanf("%s",s); l=strlen(s);
memset(f,0,sizeof(f));
for (i=0;i<l;i++) {
f[i].num=1; f[i].start[0]=0; f[i].start[1]=i+1;
for (j=0;j<i;j++)
work(j,i);
}
//print
j=0;
for (i=0;i<l;i++) {
if (i==f[l-1].start[j]) {
j++;
if (i)
printf(",");
}
printf("%c",s[i]);
}
printf("\n");
return 0;
}

var

st,ans:string;

f:array[1..80]of string;

g:array[1..80]of longint;

i,j,k,p:longint;

function dayu(st1,st2:string):boolean;

var

i,j,k:longint;

begin

while (st1[1]='0')and(st1'0') do delete(st1,1,1);

while (st2[1]='0')and(st2'0') do delete(st2,1,1);

if length(st1)>length(st2) then exit(true);

if length(st1)st2 then exit(true)

else exit(false);

end;

begin

readln(st);

for i:=1 to 80 do f[i]:='';

for i:=1 to length(st) do

begin

for j:=i-1 downto 0 do

if j=0 then f[i]:=copy(st,1,i)

else

begin

if dayu(copy(st,j+1,i-j),f[j]) then

begin

f[i]:=copy(st,j+1,i-j);

break;

end;

end;

end;

k:=length(st);ans:='';

while k0 do

begin

ans:=f[k]+','+ans;

k:=k-length(f[k]);

end;

delete(ans,length(ans),1);

writeln(ans);

end.

f前i个数用j个逗号，最后一个数的最小值

s[x,y]表示原字符串中第x个位置到第y个位置组成的数字

f=min(s[k,i])

其中要满足

1.f=s[1,i];

2.s[k,j]>f[k-1,j-1]

3.j

var st,tmp:string[80];

f:array[0..45,0..80]of string[80];

r:array[0..45,0..80]of integer;

i,j,k:integer;

for i:=2 to length(st) shr 1+5 do

for j:=i to length(st) do

for k:=i-1 to j-1 do

begin

tmp:=get(k+1,j);

if (f'')and big(tmp,f) then

begin

if f='' then

begin

f:=tmp;

r:=k;

end

else

begin;

r:=k;

f:=tmp;

end;

end;

end;

启发：字符串动归

Accepted 有效得分：100 有效耗时：0ms

AC%--

61%--58%

稀里糊涂.....

---|---|---|---|---|---|---|---|---|---|---|---|

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var j,n,i:longint;s,t,m:string;

f:array[0..120]of string;

rout:array[0..120]of longint;

function small(s,t:string):boolean;

var a,b:string;

begin

a:=s;

b:=t;

while (a[1]='0')and(length(a)>1) do delete(a,1,1);

while (b[1]='0')and(length(b)>1) do delete(b,1,1);

if length(a)length(b) then exit(false)

else

if a

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一次AC，秒杀.........

注意要输出前导零！

不必为题目中的“第一个数尽量大”所迷惑

只需正常思路的动规就可以了，因为会被更优解覆盖！

猥琐猥琐

第一次把i打成l

第二次没复制完全

第三次ac

ac率下降1

~~~~(>_

我的第121题

这道题第656个通过

回文数...= =！

主要是两个数的比较，还有要求的方案是前面的数大的，就是说方程要用>=

方程跟最长上升序列一样

每次都记录分割部分 当前要与选取分割部分之前记录的状态比较

用一个数组在他们之间做关系记录

一次A掉 多检查就是有效果啊

呜呼 ⊙﹏⊙b汗

千万别用子界类型

0..1换integer

80->AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

如果题目看仔细了可一次ac

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

复制的，蛤蛤蛤蛤蛤蛤蛤蛤

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DP...

#include

#include

#include

#define max(a,b) ((a)>(b)?(a):(b))

#define maxn 100

typedef char str[maxn];

struct type{

long d,pre;

str s;

}D[maxn][maxn]={0};

str s={0};

int B[maxn]={0};

int cmp(str s1,str s2){

long l1=strlen(s1),l2=strlen(s2);

if (l1>l2) return 1;

if (l1-1;i--) s=s[i];

D[0][0].d=1;

for (i=1;i0;j--)

for (k=0;k

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

第628人！！！（啥奶子含义？？）

对于前导零，存储状态的时候要用字符串，不然的话会~~~~~

（向前面的N位师兄一样倒楣。。。）

一轮の花

程序：

http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!144.entry

BS出题人……不是我程序差……主要是没说明‘0’的问题！！！害得我提交那么多次！哼！

{—————————————————}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

字符串比较大小的时候千万小心删去前导的"0"！！！！

我AC了来看题解才发现想得太麻烦了。0的问题搞错了。。

晒晒程序。。

f为前i位最后一个数长为j时最多能分成几个。

积累RP

program v1306;

var

max,last,i,j,k,n,m : longint;

s : string;

r,f : array[0..80,0..80]of longint;

procedure print(p,len,num : longint);

var

i : longint;

begin

if p=0 then exit

else

begin

print(p-len,r[p,len],num-1);

if p-len0 then write(',');

for i := p-len+1 to p do

write(s[i]);

end;

end;

function check(a,b : string): boolean;

var

i : longint;

s1,s2 : string;

begin

s1 := a;

s2 := b;

while (length(s1)>1)and(s1[1]='0') do delete(s1,1,1);

while (length(s2)>1)and(s2[1]='0') do delete(s2,1,1);

if length(s1)>length(s2) then exit(false)

else if length(s1)s2[i] then exit(false)

else if s1[i]0 then

if f+1>f then

begin

f := f+1;

r := k;

end;

end;

end;

last := 0;

max := 0;

for i := 1 to length(s) do

if f[length(s),i]>max then

begin

max := f[length(s),i];

last := i;

end;

print(length(s),last,f[length(s),last]);

writeln;

end.