1

http://www.spoj.com/problems/MMAXPER/

我不知道如何解决这个问题，因为我是 dp 问题的新手。我正在尝试这种方法但得到错误的答案::

#include<stdio.h>
int main()
  {
    int i,t,l,s,temp;
    long long int sum=0;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
      {
        scanf("%d %d",&s,&l);
        if(s>l) { temp=s; s=l; l=temp }
        if(i==1) sum=sum+l-s;
        else if(i==t && i%2==0) sum=sum+l+s;
        else if(i==t && i%2!=0) sum=sum+l-s;
        else if(i%2==0) sum=sum+2*l+s;
        else if(i%2!=0) sum=sum-2*s+l;
      }
    printf("%lld",sum);
    return 0;
  }
4

1 回答 1

2

想想你必须做出什么选择的问题。由于不允许重新排序，所以问题很简单。让我们看看：对于第 i 个矩形，您有 2 个选择，要么按原样使用它，要么旋转它。如果 p(i,0) 是第 i 个矩形在原始位置的最大周长，并且 p(i,1) 表示第 i 个矩形旋转时的最大周长，那么这会产生一个简单的递归：

p(i,0)=max(p(i-1,0)+宽度(i)+|高度(i)-高度(i-1)|,p(i-1,1)+宽度(i) +|高度(i)-宽度(i-1)|)

和

p(i,1)=max(p(i-1,0)+高度(i)+|宽度(i)-高度(i-1)|,p(i-1,1)+高度(i) +|宽度(i)-宽度(i-1)|)

最终答案是 max(p(n-1,0),p(n-1,1))

基本情况 p(0,0)=height(i) 和 p(0,1) = width(i);

说明：考虑当前，即第 i 个矩形，第 (i-1) 个矩形可以正常放置或旋转。从两种选择中获取最大周长就可以了。

希望这可以帮助

于 2013-12-19T11:34:45.083 回答