单向 DSP

【题目链接】

【题目类型】dp

&题解：

紫书P271 这块的字典序排序我觉得挺厉害的，每次都把那3步sort一下，之后if (v< d[i][j]) 这块的小于号用的很好，因为只有小于才变，而不是小于等于，所以就保证的字典序。

【时间复杂度】O(m*n)

&代码：

#include 
    
     using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;#define cle(a,val) memset(a,(val),sizeof(a))#define SI(N) scanf("%d",&(N))#define SII(N,M) scanf("%d %d",&(N),&(M))#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))#define rep(i,b) for(int i=0;i<(b);i++)#define rez(i,a,b) for(int i=(a);i<=(b);i++)#define red(i,a,b) for(int i=(a);i>=(b);i--)const ll LINF = 0x3f3f3f3f3f3f3f3f;#define PU(x) puts(#x);#define PI(A) cout<<(A)<
     
      =0;j--){            for (int i=0;i
      
       >T;while(T--)    Solve();    return 0;}