从零开始的DP学习系列之贰(我的DP真的就这么烂TAT)

设DP状态的另一个技巧，考虑题目中有关答案的各种信息

然后这种和结尾有关系的$dp$可以考虑向前找结尾来转移

设$dp[i][j]$表示到第$i$天为止，有$j$天有奶牛逃跑的最小不一致记录数。转移时枚举天数和逃跑天数，然后枚举一个前一个逃跑的天数$k$，从$dp[i-1][k]$以一个$dif[k+1][i]$的代价转移过来。其中$dif[i][j]$表示从第$i$天到第$j$天中与记录不一致的数目。这样直接做是$O(n^4)$的，不过这个$dif$显然可以$O(n^2)$预处理，然后时间复杂度就降到了$O(n^3)$

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=105; 6 int num[N],dif[N][N],dp[N][N],n; 7 int main () 8 { 9     scanf("%d",&n);10     for(int i=1;i<=n;i++)11         scanf("%d",&num[i]);12     for(int i=1;i<=n;i++)13     {14         int tmp=0;15         for(int j=i;j<=n;j++)16             dif[i][j]=(tmp+=(num[j]!=j-i));17     }18     memset(dp,0x3f,sizeof dp); dp[0][0]=0;19     for(int i=1;i<=n;i++)20         for(int j=1;j<=i;j++)21             for(int k=0;k