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 に答える