SPOJ MMAXPER：：矩形周长

Question

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;
  }

Answer 1

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

高度p(i-1，1)+宽度(I)+|高度(I)-width(i-1)|)

和

宽度p(i-1，1)+高度(I)+|宽度(I)-width(i-1)|)

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

基例p(0，0)=高度(I)，p(0,1) =宽度(I)；

说明:考虑到电流，即第i个矩形，第(i-1)个矩形可能被正常放置或旋转。从两个选择中取最大周长可以解决问题。

希望这能有所帮助