03  hdu 5009 Paint Pearls

题目意思：

有n颗珍珠，要求每颗珍珠达到预定颜色，每次操作可以选一连续区间的珍珠，让它们达到预定颜色，花费为该区间不同颜色种数的平方。求完成任务的最少花费。

n<=5*10^4

解题思路：

dp+数据结构

o(n^2)肯定会超时.考虑花费最多为n,且最大的种数为sqrt(n),可以一种一种的往前扫(不是一个一个的),注意如果后面已经选了某种，则前面的该种不用扫，直接连到前面去，用一个并查集维护可以连续跳的最前面的那个，直到开辟一种新的颜色。根表示可以跳到的最前的位置。

代码：

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 51000

int Fa[Maxn],nu[Maxn],sa[Maxn],temp[Maxn],la[Maxn];
int n,dp[Maxn];

int Find(int x)
{
    while(Fa[x]!=x)
        x=Fa[x];
    return x;
}
void Unio(int a,int b)
{
    int x=Find(a),y=Find(b);

    if(x!=y)
        Fa[y]=x;  //注意是后一个连前一个
}

int main()
{
    //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   while(~scanf("%d",&n))
   {
       Fa[0]=0;
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&sa[i]);
           temp[i]=sa[i];
           Fa[i]=i;
       }
       sort(temp+1,temp+n+1);
       int cnt=unique(temp+1,temp+n+1)-temp;
       map<int,int>myp;
       for(int i=1;i<=cnt;i++)
       {
           myp[temp[i]]=i;  //标记某数是第几大
           la[i]=-1;
       }
       for(int i=1;i<=n;i++)
            nu[i]=myp[sa[i]]; //标记该数的大小序

       dp[0]=0;
       for(int i=1;i<=n;i++)
       {
           if(la[nu[i]]!=-1)
               Unio(la[nu[i]]-1,la[nu[i]]);
          la[nu[i]]=i;
          dp[i]=i;
          int num=0;

          for(int j=i;j>0;j=Find(j-1)) //一种一种的往前移动,如果后面选了，可以连续往前跳
          {
              num++;
              if(num*num>=dp[i])
                    break;
              int nn=Find(j-1);
              dp[i]=min(dp[i],dp[nn]+num*num);

          }

       }
       printf("%d\n",dp[n]);





   }

    return 0;
}

题目意思：

告诉一个矩阵的第一行和第一列，按照sa[i][j]=sa[i-1][j]+sa[i][j-1]的运算规则求出sa[n][m].

n<=10 m<=10^9

解题思路：

矩阵快速幂。

一列一列的往前推。构造递推矩阵。

矩阵构造示意图：

代码：

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 10000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 15

int n,m;

struct Mar
{
    int row,col;
    ll s[Maxn][Maxn];

    void init(int a,int b)
    {
        row=a,col=b;
        memset(s,0,sizeof(s));
    }
};

Mar operator * (const Mar &a,const Mar &b)
{
    Mar res;
    res.init(a.row,b.col);

    for(int k=1;k<=a.col;k++)
    {
        for(int i=1;i<=res.row;i++)
        {
            if(a.s[i][k]==0)
                continue;
            for(int j=1;j<=res.col;j++)
            {
                if(b.s[k][j]==0)
                    continue;
                res.s[i][j]=(a.s[i][k]*b.s[k][j]+res.s[i][j])%M;
            }
        }
    }
    return res;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(!n&&!m)
        {
            printf("0\n");
            continue;
        }
        Mar ba;
        ba.init(n+2,n+2);

        ba.s[1][1]=10;
        ba.s[1][n+2]=3;
        for(int i=2;i<=n+1;i++)
            for(int j=1;j<=i;j++)
                ba.s[i][j]=1;
        ba.s[n+2][n+2]=1;

        Mar ans;
        ans.init(n+2,1);
        ans.s[1][1]=233;
        for(int i=2;i<=n+1;i++)
            scanf("%I64d",&ans.s[i][1]);
        ans.s[n+2][1]=1;

        int k=m;
        while(k>0)
        {
            if(k&1)
                ans=ba*ans;
            k>>=1;
            ba=ba*ba;
        }
        if(n==0)
            printf("%I64d\n",ans.s[n+1][1]/10);
        else
        printf("%I64d\n",ans.s[n+1][1]);
    }
    return 0;
}

[2014 西安网络赛]