dnc opt아님?


완탐으로 opt값 non decreasing 한 것도 확인했는데 


왜 완탐코드랑 dnc 코드랑 답이 다르게 나오는지 모르겠음. opt값만 non decreasing하면 항상 dnc 쓸 수 있는거 아닌가



혹시 dnc를 잘못짰을지도 몰라서 코드 올림




#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> pi;

const int sz = 3000; 

ll X[sz+5],Y[sz+5];

ll C[sz+5][sz+5];

ll dp[3005][3005];

void DnC(int t,int l,int r,int s,int e){

if(l>r) return;

int m = (l+r)>>1;

int opt = -1;

ll&R = dp[t][m];

R = INT64_MIN/100;

for(int i=s; i<=min(e,m-1); i++){

ll pre = dp[t][m];

R = max(R,dp[t-1][i]+C[i+1][m]);

if(pre < R) opt = i;

}

DnC(t,l,m-1,s,opt);

DnC(t,m+1,r,opt,e);


}

int main(){

ios_base::sync_with_stdio(0); cin.tie(0);

srand(time(NULL));

int n,m;

cin>>n>>m;

if(n==m){

cout<<0;

return 0;

}

for(int i=1; i<=m; i++){

int a,b; cin>>a>>b;

X[i] = a - b;

Y[i] = a + b;

}

for(int i=1; i<=m; i++){

ll xmin = X[i],xmax = X[i];

ll ymin = Y[i],ymax = Y[i];

for(int j=i+1; j<=m; j++){

xmin = min(xmin,X[j]);

xmax = max(xmax,X[j]);

ymin = min(ymin,Y[j]);

ymax = max(ymax,Y[j]);

C[i][j] = max(xmax-xmin,ymax-ymin);

}

}

for(int i=1; i<=m; i++) dp[1][i] = C[1][i];

for(int i=2; i<=n; i++){

for(int j=1; j<i; j++) dp[i-1][j] = INT64_MIN/100;

DnC(i,i,m,i-1,m-1); 

}

cout<<dp[n][m];

}