Chrysanthemum's Blog

首先[tex]\sqrt n[/tex]枚举答案长度，在n枚举起点。接下来就是验证是否可行了。一开始想了一个错误的贪心，还自以为能A。。。

其实我们可以用区间DP来判断。

首先我们定义一下完美匹配。区间[i,j]是完美匹配当且仅当在用最优的方法删去一些模式串后，剩余的是模式串的前缀。显然如果区间长度是模式串的长度倍数又是完美匹配，那就符合条件。

完美匹配可以这样转移，将[i,j]分为[i,k],[k+1,j]只要两段都是完美匹配且至少有一段的长度是区间长度的倍数，这是一种转移。

还有一种转移是，[i,j-1]是完美匹配，且j处的字符为[i,j-1]的前缀的下一位，也就是模式串的第(（j-i)%len+1)位，len是模式串的长度。

这样转移是l/len的复杂度的，加点乱七八糟的优化就能过了。

代码：

#include<set>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int T,l,ans;
int f[210][210];
set<string> st;
char s[510],str[510];
int compare(int x,int len)
{
    for (int i=0;i<len;i++)
        if (s[i+x]>str[i]) return 1;else
        if (s[i+x]<str[i]) return -1;
    return 0;
}
void judge(int len)
{
    if (len>ans) return;
    for (int L=0;L<l;L++)
    if (L+len-1==l) break;else
    if (s[L]==s[0]&&s[L+len-1]==s[l-1])
    {
        string s1;
        s1.clear();
        for (int i=0;i<len;i++)
            s1+=s[L+i];
        if (st.count(s1)) continue;
        st.insert(s1);
        memset(f,0,sizeof(f));
        for (int i=0;i<l;i++) if (s[i]==s[L]) f[i][i]=1;
        for (int p=2;p<=l;p++)
            for (int i=0;i<l-p+1;i++)
            {
                int j=i+p-1;
                f[i][j]|=f[i][j-1]&(s[L+(p-1)%len]==s[j]);
                if (f[i][j]) continue;
                for (int k=1;k<=p/len;k++)
                {
                    f[i][j]|=f[i][i+k*len-1]&f[i+k*len][j];
                    f[i][j]|=f[j-k*len+1][j]&f[i][j-k*len];
                    if (f[i][j]) break;
                }
            }
        if (f[0][l-1])
        {
            if ((len<ans)||(len==ans&&(compare(L,len)<0)))
            {
                ans=len;
                for (int i=0;i<len;i++)
                    str[i]=s[L+i];
            }
        }
    }
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",s);
        l=strlen(s);
        ans=l+1;
        st.clear();
        for (int i=1;i*i<=l;i++)
        if (l%i==0)
        {
            judge(i);
            if (i*i!=l) judge(l/i);
        }
        for (int i=0;i<ans;i++)
            printf("%c",str[i]);
        printf("\n");
    }
}

我们见转换一下模型，把a,b当成x，d当成y，建立平面直角坐标系。首先离散a，b。然后就发现好像可以用区间dp。

f[i][j]表示，处理时间i~j（i，j为离散后的值），需要的最小花费。

那么我们暴力找完全在这个区间里的最高区间（也就是d最大）k。然后枚举k在哪个时间被炸毁。

f[i][j]=min(f[i][j],f[i][h-1]+f[h+1][j]+d[k])(a[k]<=h<=b[k])

解决啦！

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,cnt,a[310],b[310],d[310],p[610],f[610][610];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i],&b[i],&d[i]);
		p[++cnt]=a[i];p[++cnt]=b[i];
	}
	sort(p+1,p+cnt+1);
	cnt=unique(p+1,p+cnt+1)-p-1;
	for (int i=1;i<=n;i++)
	{
		a[i]=lower_bound(p+1,p+cnt+1,a[i])-p;
		b[i]=lower_bound(p+1,p+cnt+1,b[i])-p;
	}
	memset(f,10,sizeof(f));
	for (int i=1;i<=cnt;i++)f[i][i-1]=0;
	for (int p=1;p<=cnt;p++)
		for (int i=1;i<=cnt-p+1;i++)
		{
			int j=i+p-1;
			int maxh=0,h=0;
			for (int k=1;k<=n;k++)
			if (a[k]>=i&&b[k]<=j&&d[k]>maxh){maxh=d[k];h=k;}
			if (!h) f[i][j]=0;else
			{
				for (int k=a[h];k<=b[h];k++)
					f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+maxh);
			}
		}
	printf("%d\n",f[1][cnt]);
}