【♂Not The Triumph♂O(∩_∩)O哈哈~But The Struggle♂】

竞赛决不是捷径,它只是另一种艰辛的生活方式。得到与失去,只有时间会去评判;成功与失败,只有历史能去仲裁。我不会永远成功,正如我不会永远失败一样

  C++博客 :: 首页 :: 联系 ::  :: 管理
  6 Posts :: 239 Stories :: 25 Comments :: 0 Trackbacks

常用链接

留言簿(7)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 108800
  • 排名 - 230

最新评论

阅读排行榜

评论排行榜

Description
给定一个具有n(n<=50)个顶点(从1到n编号)的凸多边形,每个顶点的权均已知。问如何把这个凸多边形划分成n-2个互不相交的三角形,使得这些三角形顶点的权的乘积之和最小?

Input
第一行为顶点数n,第二行为n个顶点(从1到n)的权值(均小于longint)。

Output
只有一行为最小的和的值。

Sample Input
5
121 122 123 245 231

Sample Output
12214884

【参考程序】:

#include<cstring>
#include
<cstdio>
using namespace std;

typedef 
long long array[60];
array F[
110][110],a,s1,s2,s3;
long long n;
void mark(array &c)
{
    
for (int i=1;i<=c[0];i++)
    {
        c[i
+1]+=c[i]/100000;
        c[i]
%=100000;
    }
    
while (c[c[0]+1])
    {
        c[
0]++;
        c[c[
0]+1]+=c[c[0]]/100000;
        c[c[
0]]%=100000;
    }
}
void mul(long long a1,long long a2,long long a3,array &c)
{
    memset(c,
0,sizeof(c));
    c[
0]=c[1]=1;
    
for (int i=1;i<=c[0];i++) c[i]*=a1;
    mark(c);
    
for (int i=1;i<=c[0];i++) c[i]*=a2;
    mark(c);
    
for (int i=1;i<=c[0];i++) c[i]*=a3;
    mark(c);
}
void add(array a,array b,array &c)
{
    memset(c,
0,sizeof(c));
    
if (a[0]>b[0]) c[0]=a[0];
    
else c[0]=b[0];
    
for (int i=1;i<=c[0];i++) c[i]=a[i]+b[i];
    mark(c);
}
bool check(array a,array b)
{
    
if (a[0]<b[0]) return false;
    
if (a[0]>b[0]) return true;
    
for (int i=a[0];i>=1;i--)
        
if (a[i]<b[i]) return false;
        
else if (a[i]>b[i]) return true;
    
return false;
}
int main()
{
    
//freopen("data5.in","r",stdin);
    
//freopen("data5.out","w",stdout);
    scanf("%lld",&n);
    
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    
for (int i=1;i<=n;i++)
        
for (int j=1;j<=n;j++)
            F[i][j][
0]=1;
    
for (int i=n-2;i>=1;i--)
        
for (int j=i+2;j<=n;j++)
        {
            F[i][j][
0]=60;
            
for (int k=i+1;k<=j-1;k++)
            {
                mul(a[i],a[k],a[j],s1);
                add(F[i][k],F[k][j],s2);
                add(s1,s2,s3);
                
if (check(F[i][j],s3))
                    memcpy(F[i][j],s3,
sizeof(F[i][j]));
            }
        }
    printf(
"%lld",F[1][n][F[1][n][0]]);
    
for (int i=F[1][n][0]-1;i>=1;i--) printf("%05lld",F[1][n][i]);
    printf(
"\n");
    
return 0;
}


 

posted on 2009-08-17 19:30 开拓者 阅读(474) 评论(0)  编辑 收藏 引用 所属分类: 动态规划&背包经典习题

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理