DP+记录路径:
#include<fstream>
using namespace std;
int n,m;
int a[101];
int f[101][101];
int p[101][101];
int main()
{
ifstream cin("book.in");
ofstream cout("book.out");
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=n-1;i>=1;--i)
a[i]+=a[i+1];
memset(f,0x7F,sizeof(f));
for(int i=1;i<=n;++i){
f[1][i]=a[i];
p[1][i]=n;
}
int tmp;
for(int k=2;k<=m;++k)
for(int i=n-k+1;i>=1;--i){
f[k][i]=f[k-1][i];
for(int j=i+1;j<=n;++j){
if(f[k-1][j]>a[i]-a[j])
tmp=f[k-1][j];
else
tmp=a[i]-a[j];
if(f[k][i]>tmp){
f[k][i]=tmp;
p[k][i]=j-1;
}
}
}
tmp=1;
for(int i=m;i>=1;--i){
cout<<tmp<<" "<<p[i][tmp]<<endl;
tmp=p[i][tmp]+1;
}
return 0;
}
贪心：
#include<fstream>
using namespace std;
struct arr{
int x,y;
}p[101];
int n,m;
int a[101];
int f[101][101];
int main()
{
ifstream cin("book.in");
ofstream cout("book.out");
cin>>n>>m;
a[0]=0;
memset(f,0x7F,sizeof(f));
for(int i=1;i<=n;++i){
cin>>a[i];
a[i]+=a[i-1];
f[1][i]=a[i];
}
int tmp;
for(int k=2;k<=m;++k)
for(int i=k;i<=n;++i)
for(int j=k-1;j<=i-1;++j){
if(f[k-1][j]>a[i]-a[j])
tmp=f[k-1][j];
else tmp=a[i]-a[j];
if(f[k][i]>tmp)
f[k][i]=tmp;
}
//cout<<f[m][n]<<endl;
tmp=a[n];
int i=m,j=n;
memset(p,0,sizeof(p));
while(tmp){
while(j&&p[i].x+a[j]-a[j-1]<=f[m][n]){
p[i].x+=a[j]-a[j-1];
p[i].y++;
tmp=tmp-(a[j]-a[j-1]);
j--;
}
i--;
}
tmp=1;
for(int k=1;k<=m;++k){
cout<<tmp<<" "<<tmp+p[k].y-1<<endl;
tmp+=p[k].y;
}
return 0;
}
二分法(pascal)：
program book;
type
rec=record
num,pos:longint;
end;
var
m,k,i:longint;
bo:array[1..550]of longint;
data:array[1..550,0..550]of rec;
procedure qiu(be,pe:longint);
var
i,t,tt,j,t2:longint;
begin
if (pe=0)and(be<=m) then
begin
data[be,pe].num:=maxlongint;exit;
end else
if (pe=0)and(be>m) then
begin
data[be,pe].num:=0;exit;
end;
t:=0;
tt:=maxlongint;
for i:=be to m-pe+1 do
begin
t:=t+bo[i];
if data[i+1,pe-1].num=0 then qiu(i+1,pe-1);
if data[i+1,pe-1].num>t then t2:=data[i+1,pe-1].num else t2:=t;
if t2<tt then begin tt:=t2;j:=i;end;
end;
data[be,pe].num:=tt;
data[be,pe].pos:=j;
end;
procedure print;
var
i,j:longint;
begin
write(1,' ');
i:=1;
j:=k;
while j>1 do
begin
writeln(data[i,j].pos);
write(data[i,j].pos+1,' ');
i:=data[i,j].pos+1;
j:=j-1;
end;
writeln(m);
end;
begin
assign(input,'book.in');
assign(output,'book.out');
reset(input);rewrite(output);
read(m,k);
if (m=k)and(m=0) then
begin
close(output);halt;
end;
for i:=1 to m do
begin
read(bo[i]);
end;
qiu(1,k);
print;
close(output);
end.
posted on 2009-04-20 12:34
xfstart07 阅读(305)
评论(0) 编辑 收藏 引用 所属分类:
代码库