[bzoj] 1068 压缩 || 区间dp

原题

f[i][j][0/1]表示i-1处有一个M，i到j压缩后的长度，0/1表示i到j中有没有m。

初始为j-i+1
f[i][j][0]=min(f[i][j][0],f[i][k][0]+j-k)
f[i][j][1]=min(f[i][j][1],f[i][k][1]+j-k)
f[i][j][1]=min(f[i][j][1],f[i][k][1]+f[k+1][j][1]+1)
判断i,k,j，如果k+1到j可以由i到k重复得到，那么f[i][j][0/1]=min(f[i][j][0/1],f[i][k][0]+1)

#include
#include
#include
#define N 55
using namespace std;
int f[N][N][2],l;
char s[N];

bool check(int i,int j,int k)
{
    for (int q=0;q>1,t=(d+1)>>1;
		if (check(i,k+1,t))
		{
		    f[i][j][1]=min(f[i][j][1],f[i][k][0]+1);
		    f[i][j][0]=min(f[i][j][0],f[i][k][0]+1);
		}
	    }
	}
    printf("%d\n",min(f[1][l][0],f[1][l][1]));
    return 0;
}