[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
	

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据