03 hdu5009
状态转移方程很好想，dp[i] = min(dp[j]+o[j~i]^2,dp[i]) ,o[j~i]表示从j到i颜色的种数。
普通的O（n*n）是会超时的，可以想到o[]最大为sqrt(n),问题是怎么快速找到从i开始往前2种颜色、三种、四种。。。o[]种的位置。
离散化之后，可以边走边记录某个数最后一个出现的位置，初始为-1，而所要求的位置就等于
if(last[a[i]]==-1) 该数没有出现过，num[i][1] = i,num[i][j+1] = num[i-1][j];
else last[a[i]]之前 num[i][1] = i,num[i][j+1] = num[i-1][j],之后num[i][j]= num[i-1][j];
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define N 50010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
int a[N];
int dp[N];
int num[][],last[N];
map<int,int>f;
int main()
{
int i,j,n;
while(scanf("%d",&n)!=EOF)
{
f.clear();
int g = ;
for(i = ; i<= n ;i++)
{
scanf("%d",&a[i]);
if(!f[a[i]])
{
f[a[i]] = ++g;
a[i] = g;
}
else a[i] = f[a[i]];
}
for(i = ; i <= n; i++)
dp[i] = INF;
memset(last,-,sizeof(last));
memset(num,,sizeof(num));
int k = sqrt(n*1.0)+;
int tk = ;
dp[] = ;
last[a[]] = ;
num[][] = ;
dp[] = ;
for(i = ; i <= n ;i++)
{
if(last[a[i]]==-)
{
tk+=;
num[i%][] = i;
for(j = ; j <= min(tk-,k-) ; j++)
num[i%][j+] = num[(i-)%][j];
}
else
{ num[i%][] = i;
for(j = ; j < min(k,tk) ; j++)
{
if(last[a[i]]==num[(i-)%][j]) break;
num[i%][j+] = num[(i-)%][j];
}
for(int g = j+ ; g <= min(tk,k) ; g++)
num[i%][g] = num[(i-)%][g];
}
last[a[i]] = i;
for(j = ; j <= min(k,tk); j++)
{
int po = num[i%][j+];
dp[i] = min(dp[i],dp[po]+j*j);
// cout<<dp[po]<<" "<<po<<endl;
}
}
printf("%d\n",dp[n]); }
return ;
}
09 hdu5015
构造矩阵
先构造出1*(n+2)的矩阵 （233, 233+a1, 233+a1+a2, 233+a1+a2+a3, ..., 233+a1+a2+..+an, 1),表示第一列上的值。
此矩阵为A，然后想要使A*B = C，C为第二列的值，所以B可以为
10 10 10 10 10 .......0
0 1 1 1 1........0
0 0 1 1 1........0
0 0 0 1 1........0
0 0 0 0 1........0
3 3 3 3 3........1
然后快速幂就可以了。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 12
#define LL __int64
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
#define mod 10000007
struct Mat
{
LL mat[N][N];
};
int n;
int a[N];
Mat operator * (Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
int i,j,k;
for(k = ; k < n ; k++)
{
for(i = ; i < n ; i++)
{
if(a.mat[i][k]==) continue;//优化
for(j = ; j < n ; j++)
{
if(b.mat[k][j]==) continue;//优化
c.mat[i][j] = (c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod;
}
}
}
return c;
}
Mat operator ^(Mat a,int k)
{
Mat c;
int i,j;
for(i = ; i < n ; i++)
for(j = ; j < n ; j++)
c.mat[i][j] = (i==j);
for(; k ; k >>= )
{
if(k&) c = c*a;
a = a*a;
}
return c;
}
int main()
{
int m,i,j;
Mat c;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(c.mat,,sizeof(c.mat));
for(i = ; i <= n; i++)
{
c.mat[][i] = ;
for(j = ; j <= i ; j++)
c.mat[j][i] = ;
}
for(i = ; i <= n ; i++)
c.mat[n+][i] = ;
c.mat[n+][n+] = ;
LL s = ;
Mat ans;
memset(ans.mat,,sizeof(ans));
ans.mat[][] = s;
for(i = ; i <= n; i++)
{
scanf("%d",&a[i]);
s+=a[i];
s%=mod;
ans.mat[][i] = s;
}
ans.mat[][n+] = ;
int tn = n;
n+=;
if(m>)
ans = ans*(c^(m-));
// for(i = 0 ; i < n ; i++)
// {for(j = 0; j< n ; j++)
// cout<<c.mat[i][j]<<" ";
// puts("");
// }
// for(i = 0 ; i < n ; i++)
// {
// for(j = 0; j < n ; j++)
// cout<<ans.mat[i][j]<<" ";
// puts("");
// }
printf("%I64d\n",ans.mat[][tn]);
}
return ;