[DP][转化目标] UVa 1289 Stacking Plates

附上一个讲的很好的链接https://blog.csdn.net/hao_zong_yin/article/details/79807322

第一感觉是类似矩阵连乘的那种操作，写完了才意识到复杂度会是2500^3，然后果断tle了（Final的题怎么会这么简单）。然后就没有什么太好的思路了。看了题解才有点明白。

这个题第一个难点在于，他又有分割又有合并，同时考虑这两种操作的话会很难设计状态转移，但是其实可以发现这两种操作的数量是有联系的，因为最初的堆数量是确定的，最后的堆数为1，所以分割和合并的数量关系可以确定出来，这样的话只需要算出来其中一种操作的数量就可以了，我这里考虑的是合并的次数w，经过推导可以得出最后答案ans与w的关系是 ans=2*w+n-1;（这个东西其实可以很简单的算出来：直接把每一摞盘子全到一起，总共的join次数为n-1，split次数为0；然后，每次在某一摞盘子内部进行一次split操作，则必然会在最后的结果中引入一次join操作，有一一对应的关系，因此可以推出来对于任意情况都有join次数==split次数+n-1）

第二个难点就是确定了要求合并的次数之后，如何进行dp。这里我们可以借鉴汉诺塔的思想，在考虑前i个（从小到大）盘子的时候，可以把大于i的盘子当成没有一样。而由于这里我关心的只是合并次数，所以不用考虑盘子的中间态（汉诺塔里盘子只能放在某个轴上，但是这里也可以放在地上），这样的话递推方程就会变得简单了。。。只需要使得dp[i][j]表示前i个盘子全放在第j堆上（想象一下这个画面）的最小操作数（这里要求第j堆必须有i这种盘子，说”这种”是因为离散化了），则转移的时候dp[i][j]一定是从dp[i-1][k]得来，其中1<=k<=n，而这时候又有不同的情况需要讨论 ：①j==k，这时候如果有i的堆的数量为1，那么就是第j堆这个（因为我们规定只有j堆有i的时候才往这里转移），那么他就不需要动，直接dp[i][j]=dp[i-1][j]；如果有i的堆的数量大于1，那就得先把j堆上的 (1到i-1) 这一坨移走，再把其他cnt[i]-1个i类盘子合并到j堆上，再把移走的 (1到i-1) 那一坨移回来（cnt[i]代表有多少堆含有i这个种类，可以预处理出来），所以总共增加的的操作数是cnt[i]-1+1=cnt[i]，也就是这里的方程为dp[i][j]=min(dp[i-1][k]+cnt[i]);     ②  j!=k  ，这时候好说，只需要考虑第k堆有没有i就可以了，如果有那就多了cnt[i]-1次操作，如果没有就多了cnt[i]-1+1次操作（注意约定是j堆一定有一个才能往那儿转移，所以除了那一堆里的那个i，还剩下cnt[i]-1个i）。

其他的也就是离散化的操作需要谨慎一点，我由于写错这个wa了两发。。。去重的时候先保留能保留的再去重！不然有可能导致数组扫描完了却没有存任何一个数（比如整个数组都是同一个数）

 

更：今天起床看了看2个月之前做的这个题，觉得当时还是naive，每次直接考虑只向含有第i种盘子的摞转移就好了，于是重写了第二种代码（其实核心思想完全一样的）

#include

using namespace std;
const int maxn=50+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
typedef long long LL;

int ps[2505],cp;

int Hash(int x)
{
    return lower_bound(ps+1,ps+1+cp,x)-ps;
}

int pl[maxn][maxn],cnt[2505];
bool has[55][2505];
int dp[2505][55];

void pre(int n)
{
    memset(has,0,sizeof(has));
    memset(cnt,0,sizeof(cnt));
    int tp;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=pl[i][0];j++)
        {
            tp=Hash(pl[i][j]);
            has[i][tp]=1;
            cnt[tp]++;
            while(j<=pl[i][0]&&pl[i][j]==pl[i][j+1])j++;//error2
            if(j>pl[i][0])break;
        }
    }
}

int Dp(int n)
{
    memset(dp,INF,sizeof(dp));
    for(int i=1;i<=n;i++)if(has[i][1])
        dp[1][i]=cnt[1]-1;
    for(int i=2;i<=cp;i++)
    {
        for(int j=1;j<=n;j++)if(has[j][i])
        {
            for(int k=1;k<=n;k++)
            {
                if(k==j)
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+(cnt[i]==1?0:cnt[i]));//error1
                else
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+cnt[i]-has[k][i]);
            }
        }
    }

    int ans=INF;
    for(int i=1;i<=n;i++)if(has[i][cp])
        ans=min(ans,dp[cp][i]);
    return 2*ans-n+1;
}

int main()
{
    int cs=0;
    int n,sum;
    while(~scanf("%d",&n))
    {
        cs++;
        cp=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&pl[i][0]);
            sum+=pl[i][0];
            for(int j=1; j<=pl[i][0]; j++)
                scanf("%d",&pl[i][j]),ps[++cp]=pl[i][j];
        }
        sort(ps+1,ps+1+cp);
        int cnt=cp;
        cp=1;
        for(int i=2;i<=cnt;i++)
        {
            while(i<=cnt&&ps[cp]==ps[i])i++;
            if(i<=cnt)
                ps[++cp]=ps[i];
        }
        pre(n);
        printf("Case %d: %d\n",cs,Dp(n));
    }
    return 0;
}

#第二种
#include

using namespace std;

const int maxn=2505;
const int mod =1e9+7;
const int INF=0X3f3f3f3f;

vector stock[55];
int dp[maxn][55];
int cnt[maxn],has[55][maxn];

int cnt1,cx[maxn];
int HashX(int m)
{
    return lower_bound(cx+1,cx+1+cnt1,m)-cx;
}

int main()
{
    int n,h,tmp,cs=0;
    vector tpv;
    while(~scanf("%d",&n))
    {
        cs++;
        memset(dp,INF,sizeof(dp));
        memset(has,0,sizeof(has));
        memset(cnt,0,sizeof(cnt));
        cnt1=0;
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&h);
            stock[i].clear();
            for (int j=1; j<=h; j++)
            {
                scanf("%d",&tmp);
                stock[i].push_back(tmp);
                cx[++cnt1]=tmp;
            }
        }
        sort(cx+1,cx+1+cnt1);
        int cnt2=cnt1;
        cnt1=1;
        for (int i=2; i<=cnt2; i++)
            if (cx[i]!=cx[cnt1])
                cx[++cnt1]=cx[i];
        for (int i=1; i<=n; i++)
        {
            int len=stock[i].size();
            for (int j=0; j1)
            {
                tpv.clear();
                tpv.push_back(stock[i][0]);
                int pt=0;
                for (int j=1; j