가로등 을 끄다

이 문제에 대해 나는 그의 알이 아픈 순환이 무슨 뜻인지 완전히 이해하지 못했다. 여기에는 아주 잘 쓴 문제 한 편을 붙여서 풀 수 있을 뿐이다.
컨텐트는 다음과 같습니다.
이것은 구간형의 동적 기획 문제이다.
나는 주로 전방의 몇몇 dp문제에 대해 약간의 세부 사항을 보충한다.
기왕 동규라면 먼저 자주 사용하는 작성법과 브러쉬법에 대해 이야기하자.
메모법은 상태 전이 방정식과 이전 상태를 이용하여 나타난 상태를 유도하는 것이다(이미 알고 있는 조건을 알고 답안을 채우는 것과 같다)
브러시법은 현재의 상태를 이용하여 관련된 다음 상태를 모두 밀어내는 것이다.
이 문제는 내가 선택한 것이 기입법이다.
제목의 대의를 이해하다.
불을 끄는 데는 별도의 시간이 필요 없고, 불이 지나가면 꺼진다.하지만 되돌아가서 큰 불을 끄는 것이 아래로 내려가서 끄는 것보다 더 좋을 수도 있고,
그러면 두 가지 상태를 얻을 수 있다.
우리가 필요로 하는 전체 전등 과정 중의 최우수치(최소 에너지 소모)
그러면 설계해야 할 상태 이동 방정식에는 틀림없이 두 가지 방안이 있을 것이다(되돌아오는, 벽에 부딪히지 않고 돌아오지 않는)
또한 특정 구간의 불을 끄는 과정에서 에너지 소모가 가장 적기 때문에 하나의 구간으로 바꾸어 쓸 수 있다.
어떤 구간의 불을 끄면 거리 전체가 이 구간의 불을 제외하고는 점차 꺼질 것이고 다른 것은 틀림없이 모두 밝을 것이다.
그러면 우리는 f[i][j]를 i에서 j까지의 불이 모두 꺼진 후에 남은 불의 총 출력으로 기억한다.
한 걸음 더: f[i][j][0]는 i에서 j까지의 불을 끄면 라오쟝은 i점에 서고, f[i][j][1]는 [i][j]의 불을 끄면 라오쟝은 오른쪽 끝에 서고
(i는 왼쪽 끝, j는 오른쪽 끝)
또 f[i][j][0]는 두 가지 방안에서 유도된다(위에 쓰여 있다.):되돌아와서 i, j의 등불을 끄고 i+1에서 깊이 들어가 i개의 등불을 계속 끄고 (i, j)까지 확장한다.
그래서 상태 이동 방정식을 얻는다.
f[i][j][0] = min ( f[i+1][j][0] + ( a[i+1] - a[i] ) * ( sum[i] + sum[n] - sum[j] ) , f[i+1][j][1] + ( a[j]-a[i] ) * ( sum[i]+sum[n]-sum[j]) );
f[i][j][1] = min ( f[i][j-1][0] + ( a[j] - a[i] ) * ( sum[i-1] + sum[n] - sum[j-1] ) , f[i][j-1][1] + ( a[j]-a[j-1] ) * ( sum[i-1] + sum[n] - sum[j-1] ) );
(지금의 가로등 l(2-n, c위의 가로등이 꺼졌기 때문), i+l-1<=n(길은 이렇게 길다), j=i+l-1(오른쪽 끝))
왜냐하면 마지막에 장씨가 왼쪽 단점이 가장 좋은지 오른쪽 단점이 가장 좋은지 몰랐거든요.
그래서 f[1][n][0]와 f[1][n][1]에서min 출력을 얻는다.
코드 첨부(설명 포함)

#include 
#include 
using namespace std;
const int MAXM=60;
int a[MAXM],b[MAXM],sum[MAXM],n,m,c;
int f[MAXM][MAXM][2];
int min(int a,int b)//         ：  max min     ，          
{return aint max(int a,int b)
{return a>b?a:b;}
int main()
{
  scanf("%d%d",&n,&c);
  memset(f,127,sizeof(f));//          min   
  for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i],&b[i]),sum[i]=sum[i-1]+b[i];
  f[c][c][0]=f[c][c][1]=0;//    （   ）
  for(int l=2;l<=n;l++)
    for(int i=1;i+l-1<=n;i++)
      {
    int j=i+l-1;
    f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*(sum[i]+sum[n]-sum[j]),//         ？
               f[i+1][j][1]+(a[j]-a[i])*(sum[i]+sum[n]-sum[j]));//   j        ？（    [i+1][j]  ，i ， j       i）
//       sum[n]-(sum[j]-sum[i])    i       ，          i    
    f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*(sum[i-1]+sum[n]-sum[j-1]),//  
               f[i][j-1][1]+(a[j]-a[j-1])*(sum[i-1]+sum[n]-sum[j-1]));
        }
  int ans=min(f[1][n][0],f[1][n][1]);
  printf("%d",ans);
  return 0;
}