普及组第一题水平。。。。。数据弱的没话说
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
char a[100];
long long b[100][100],n, k, len, i, j, s;
long long mod(int l, int r)
{
long long num = 0;
int i;

for(i = l; i <= r; i++) num = num * 10 + a[i] - '0';

return num;
}
int main()
{
cin >> n >> k >> a;
len = strlen(a);
memset(b, 0, sizeof(b));
for(i = 0; i < len; i++) b[i][0] = mod(0, i);
for(i = 0; i < len; i++) for(j = 1; j <= k; j++) for(s = 0; s < i; s++) b[i][j] = max(b[i][j], b[s][j - 1] * mod(s + 1, i));
cout << b[len - 1][k];
}

n, k = ((int(x) for x in raw_input().split(' ')))
nums = raw_input()
dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
for i in range(n):
dp[i][0] = int(nums[:i + 1])
for j in range(1, k + 1):
for p in range(i):
dp[i][j] = max(dp[i][j], dp[p][j - 1] * int(nums[p + 1:i + 1]))
print dp[n - 1][k]

DP+高精度+滚动数组。。
但数据弱了点。

#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
char a[100];
long long dp[100][100];
long long get(int l,int r)
{
long long num=0;
int i;
for(i=l;i<=r;i++)
num=num*10+a[i]-'0';
return num;
}
main()
{
int n,k,len,i,j,s;
cin>>n>>k>>a;
len=strlen(a);
memset(dp,0,sizeof(dp));
for(i=0;i<len;i++)
dp[i][0]=get(0,i);
for(i=0;i<len;i++)
for(j=1;j<=k;j++)
for(s=0;s<i;s++)
dp[i][j]=max(dp[i][j],dp[s][j-1]*get(s+1,i));
cout<<dp[len-1][k];
}

var
f,sum:array[0..2000,0..2000]of longint;
s:string;
code,n,k,i,j,m:longint;
function max(a,b:longint):longint;
begin
if a>b then
exit(a)
else
exit(b);
end;
begin

readln(n,k);
read(s);
for i:= 0 to n do
for j:=0 to i do
f[i,j]:=1;
for i:=1 to n do
for j:=i to n do
val(copy(s,i,j-i+1),sum[i,j],code);
for i:=1 to n do
f[i,0]:=sum[1,i];
for i:= 1 to n do
for j:=1 to k do
for m:=j to i-1 do
f[i,j]:=max(f[i,j],f[m,j-1]*sum[m+1,i]);
writeln(f[n,k]);
end.

1A!!
F[i,j]:=max(F[i,j],f[k,j-1]+sum[k+1,i]);
sum[i,j] i~j 的数
f[i,j] 前i个数字添加j个乘号的最大乘积
Var n,k,i,j,code,m:longint;
s:string;
f,sum:array[0..100,0..100] of longint;
Function max(a,b:longint):longint;
Begin
If a>b then exit(a) else exit(b);
End;
Begin
readln(n,m);
Readln(s);
For i:=1 to length(s) do
For j:=i to length(s) do
Val(copy(s,i,j-i+1),sum[i,j],code);
For i:=0 to length(s) do
For j:=0 to m do
f[i,j]:=1;
For i:=0 to length(s) do f[i,0]:=sum[1,i];
For i:=1 to length(s) do
For j:=1 to i-1 do
For k:=j to i-1 do
f[i,j]:=max(f[i,j],f[k,j-1]*sum[k+1,i]);
Writeln(f[length(s),m]);
Readln;
End.

编译通过...

├ 测试数据 01：答案正确... (0ms, 756KB)

├ 测试数据 02：答案正确... (0ms, 756KB)

├ 测试数据 03：答案正确... (0ms, 756KB)

├ 测试数据 04：答案正确... (0ms, 756KB)

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

Accepted / 100 / 0ms / 756KB

用动态规划令d为第i个数字到第j个数字加k个乘号所能达到的最大值

DP方程：

for t:=i to j-1 do

if max

天哪。。这也秒杀？？我在RQNOJ上只有90分！

以下是程序：

var

a:array[0..100] of longint;

f:array[0..100,0..100] of qword;

h:array[0..100,0..100] of qword;

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

aa:qword;

s:string;

function max(x,y:qword):qword;

begin

if x>y then exit(x) else exit(y);

end;

begin

readln(m,n);

readln(s);

aa:=0;

for i:=1 to m do begin

val(s[i],a[i]);

aa:=aa+a[i];

f:=aa;

end;

for i:=1 to m do

for j:=i to m do h:=h*10+a[j];

for i:=1 to m do f:=h[1,i];

for j:=2 to n+1 do

for i:=1 to m do

for k:=1 to i do

f:=max(f,f[k,j-1]*h[k+1,i]);

writeln(f[m,n+1]);

end.

总觉得哪儿不对。。

编译通过...

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

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

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

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

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

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

递归

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

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

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

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

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

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

其实就是邮局问题，区间动规；

三重循环，f【i,j]表示前j个数中插i个*！！！

注意i=0 ！！！！！！单独子那个。。。。。。。

下面亮程序了::::::

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

var

str,l:string;

n,k,i,j,kk:longint;

s,max:int64;

f:array[0..100,0..100] of int64;

begin

readln(n,k);

readln(str);

for i:=0 to 100 do

for j:=0 to 100 do

f:=1;

for i:=1 to n do

val(copy(str,1,i),f[0,i]);

for i:=1 to k do

for j:=i+1 to n do

begin max:=0;

for kk:=i to j-1 do

begin

l:=copy(str,kk+1,j-kk);

val(l,s);

if f*s>max then max:=f*s;

end;

f:=max;

end;

writeln(f[k,n]);

end.

DP+高精（貌似不用，但自己还是写了，练手。。写写其实挺简单的）

f表示前i个数添j个乘号能得到的最大值

f:=MAX(f[p,j-1]*sum(p+1,j))

var

n,k:longint;

s:string;

a:array[1..100]of string;

max,smax:longint;

procedure try(nn,kk:integer; ss:string);

var i,kkk:integer;

begin

if kk=0 then

begin

a[k+1]:=ss;

smax:=1;

for i:=1 to k+1 do

begin

val(a[i],kkk);

smax:=smax*kkk;

end;

if smax>max then max:=smax;

exit;

end;

for i:=1 to nn-kk do

begin

a[k-kk+1]:=copy(ss,1,i);

try(nn-i,kk-1,copy(ss,i+1,100));

end;

end;

begin

readln(n,k);

readln(s);

try(n,k,s);

writeln(max);

end.

AC

哎，太水了……

var a:array[0..100,0..100] of longint;

b:array[0..100,0..100] of longint;

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

s:string;

function f(x,js:longint):int64;

var i:longint;

begin

if b[x,js]=0 then

if js=0 then

b[x,js]:=a[1,x]

else

for i:=1 to x-1 do

if f(i,js-1)*a>b[x,js] then

b[x,js]:=f(i,js-1)*a;

f:=b[x,js];

end;

begin

readln(n,k);

readln(s);

for i:=1 to n do

for j:=i to n do

val(copy(s,i,j-i+1),a,m);

writeln(f(n,k));

end.

编译通过...

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

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

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

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

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

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

program ex;

var i,j,n,k:longint;

s:ansistring;

a,f:array[1..40,1..6]of longint;

function max(a,b:longint):longint;

begin

if a>b then exit(a) else exit(b);

end;

procedure dp;

var i,j,t:longint;

begin

for i:=1 to n do

for j:=i to n do

val(copy(s,i,j-i+1),a);

for i:=1 to n do f:=a[1,i];

for j:=2 to k do

for i:=1 to n do

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

f:=max(f,f[t,j-1]*a[t+1,i]);

end;

begin

readln(n,k);

inc(k);

readln(s);

dp;

writeln(f[n,k]);

end.

Flag 　　 Accepted

题号 　　P1347

类型(?) 　　动态规划

通过 　　1976人

提交 　　3412次

通过率 　　58%

难度 　　2

提交 讨论 题解

编译通过...

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

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

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

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

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

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

1

program cjzd;

var i,j,n,m,k,s,t:longint;w,w1,w2,w3:string;

function pd(a,b:string):string;

var la,lb,i2:longint;

begin

la:=length(a);lb:=length(b);

if length(a)>length(b) then exit(a);

if length(b)>length(a) then exit(b);

for i2:=1 to la do begin

if a[i2]b[i2] then

begin if a[i2]>b[i2] then exit(a) else exit(b);end;

end;

pd:=a;

end;

function gc(a,b:string):string;

var jw,he,la,lb,lc,i1,j1:longint;c:string;

begin

la:=length(a);lb:=length(b);lc:=la+lb;c:='';

for i1:=1 to lc do c:=c+'0';

for i1:=la downto 1 do begin

jw:=0;

for j1:=lb downto 1 do begin

he:=(ord(a[i1])-48)*(ord(b[j1])-48)+jw+ord(c[i1+j1])-48;

jw:=he div 10;

c[i1+j1]:=char(he mod 10+48);

end;

if jw>0 then c[i1+j1-1]:=char(jw+48);

end;

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

gc:=c;

end;

function work(i,j:longint;w:string):string;

var o,o1,o2:longint;max:string;

begin

max:='0';

if j=0 then exit(w) else begin

for o:=1 to i-j do begin

w1:=gc((work(o,0,copy(w,1,o))),(work(i-o,j-1,copy(w,o+1,i-o))));

max:=pd(max,w1);

end;

work:=max;

end;

end;

begin

readln(n,k);

readln(w3);

write(work(n,k,w3));

end.

用了高精.....惭愧惭愧.....

-，-感谢神牛告诉我不用高精。。。

本来还想着用高精，但只是加了extended+DP+记忆化搜索，结果数据太弱了……

做麻烦了……

不是题水，数据太水……

var

f:array[1..40,0..6]of extended;

s:string;

i,k,n:longint;

max,j,num:extended;

function check(l,t:integer):extended;

var

i,d:longint;

max1,num:extended;

begin

max1:=0;

if f[l,t]0 then check:=f[l,t]

else

begin

if t+1>l then exit(0);

if t=0 then begin val(copy(s,1,l),num); f[l,t]:=num; check:=f[l,t]; end

else

begin

for d:=t to l-1 do

begin

val(copy(s,d+1,l-d),num);

max1:=check(d,t-1)*num;

if max1>f[l,t] then f[l,t]:=max1;

end;

check:=f[l,t];

end;

end;

end;

begin

readln(n,k);

readln(s);

fillchar(f,sizeof(f),0);

max:=check(n,k);

writeln(max:0:0);

end.