[排序][贪心][动态单调性数据结构][x] codeforces 1061D TV Shows

http://codeforces.com/contest/1061/problem/D

嗯。。。又是这种一维的区间最优化策略问题了。。。似乎已经感觉到了套路。。。（赛场上贪心有感觉就直接上了

这种题一般是先排序（以左端点或者右端点）搞出来一个顺序，然后在这个顺序的基础上逐个考虑。考察到某一段时候一般需要做决策，然后这时候可以根据具体题目来看是贪心决策还是dp，如果直觉是贪心（毕竟真正证明有时候确实不好弄），那一般决策都跟满足条件的极端值有关，比如在这里就是如果存在能合并的点（如果连最基本的两段合并后小于各买一台电视机都不满足那一定不能合并），那么一定是和这段左边最靠近他的一个点合并。具体证明可以分情况讨论，一般真的证明的时候就是得考虑，如果不这么合并，计算出来的结果和原来的结果对比，一般要考虑之后的seg的影响，在考虑的时候可以分情况讨论（反正我一般有直觉就上233

然后在实现的时候，有时候没有头绪可以想想STL！（想起了ccpc网络赛被set支配的恐惧），这个东西有时候真的有妙用，它既保持了单调的性质（可以用来贪心）又有着动态维护的特性（贪心的动态调整）。

wa点又是精度，嗯万年精度，这次竟然LL也炸了，而且是因为add的两个参数本身可以达到LL，然后一加给爆了。。。。我去

#include<bits/stdc++.h>

using namespace std;

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

vector<int> 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<int> 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; j<len; j++) { stock[i][j]=HashX(stock[i][j]); } if (len>1)
            {
                tpv.clear();
                tpv.push_back(stock[i][0]);
                int pt=0;
                for (int j=1; j<len; j++)
                    if (tpv[pt]!=stock[i][j])
                    {
                        pt++;
                        tpv.push_back(stock[i][j]);
                    }
                stock[i]=tpv;
            }
            len=stock[i].size();
            for (int j=0; j<len; j++)
                cnt[stock[i][j]]++,has[i][stock[i][j]]=1;
        }
        for (int j=1; j<=n; j++)
            dp[0][j]=0;

        for (int i=1; i<=cnt1; i++)
        {
            for (int j=1; j<=n; j++)
                if(has[j][i])
                {
                    for (int k=1; k<=n; k++)
                        if(has[k][i-1]||i==1)
                        {
                            if(j==k)
                                dp[i][j]=min(dp[i][j],dp[i-1][k]+(cnt[i]==1?0:cnt[i]));
                            else
                                dp[i][j]=min(dp[i][j],dp[i-1][k]+cnt[i]-has[k][i]);
                        }
                }
        }
        int ans=INF;
        for (int j=1; j<=n; j++)
            if(has[j][cnt1])
                ans=min(ans,dp[cnt1][j]);
        cout<<"Case "<<cs<<": "<<2*ans-n+1<<endl;
    }
    return 0;
}