主题：Help me! 重赏（^_^）
wyh
[专家分：130] 发布于 2005-06-01 21:29:00
凸多边形三角划分。给定一个N（N<50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N－2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？
输入文件：第一行为顶点数N；
第二行为N个顶点（从1到N）的权值。
输出格式：最小的和的值；
各三角形组成的方式。
输入示例：5
121、122、123、245、231
输出示例：The minimum is :12214884
The formation of 3 triangle: (划分法未知)
回复列表 （共6个回复）
沙发
methuselah [专家分：6840] 发布于 2005-06-02 09:24:00
哎,acm的题都是这样解出来的嘛?
板凳
brianzf [专家分：30] 发布于 2005-07-29 13:29:00
什么意思呀？什么叫顶点的权呀？
3 楼
我笨故我在 [专家分：0] 发布于 2005-07-29 14:28:00
用动态规划做吗！
4 楼
609236 [专家分：0] 发布于 2005-07-30 16:58:00
catalan数列
5 楼
wu1014 [专家分：0] 发布于 2006-03-01 22:51:00
program ex;
var a:array[1..20]of byte;
f,b:array[0..20,0..20]of longint;
n:byte;
procedure init;
var i:byte;
begin
assign(input,'d:\fp\p1.txt');
reset(input);
readln(n);
for i:=1 to n do read(a[i]);
fillchar(f,sizeof(f),0);
fillchar(b,sizeof(b),0);
close(input);
end;
procedure try;
var i,j,k,bj:byte;
begin
for i:=2 to n-1 do
for j:=1 to n-i do
begin
f[j,j+i]:=high(f[j,j+i]);
for k:=j+1 to j+i-1 do
if f[j,j+i]>f[j,k]+f[k,j+i]+a[j]*a[k]*a[j+i] then
begin
bj:=k;
f[j,j+i]:=f[j,k]+f[k,j+i]+a[j]*a[k]*a[j+i];
end;
b[j,j+i]:=bj;
end;
end;
procedure out(i,j:byte);
begin
if j-i>=2 then
begin
out(i,b[i,j]);
writeln(i,b[i,j],j);
out(b[i,j],j);
end;
end;
begin
init;
try;
writeln(f[1,n]);
out(1,n);
end.
6 楼
wu1014 [专家分：0] 发布于 2006-03-01 22:53:00
只要把数组改成下标改成50即可
我来回复
您所在位置：