DZY 's BLOG

求一个数表示为几个Fib[]之和的方案数。n<=10^18。

首先发现fib增长的很快。到了89就爆long long了。那么总共就88个数可用。

然后可以利用贪心从大到小得到一种方案。比如25。先从大的fib数开始取。所以25=f[7]+f[3]+f[1]=21+3+1。

用二进制来表示选中的fib数就是：1010001（从小到大）

注意到：因为fib[i]=fib[i-1]+fib[i-2]。所以001和110是等价的。那么我们就可以从第一个推到最后一个每一位可以取1也可以不取1。

如果不取1。那就有cnt/2种取法（cnt为这个1和前面一个1中间的0的个数）。然后乘法原理就行了。

dp的时候只需要枚举1的位置即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[89],a[89],n,g[89][2];	int m=0;
int main(){
	cin >> n;
	f[1]=1;	f[2]=2;
	for(int i=3;i<=88;i++)	f[i]=f[i-1]+f[i-2];
	for(int i=88;i>=1;i--)	if(f[i]<=n)	n-=f[i],a[++m]=1LL*i;
	reverse(a+1,a+m+1);
	g[1][1]=1;
	g[1][0]=(a[1]-1)>>1;
	for(int i=2;i<=m;i++){
		g[i][1]=g[i-1][0]+g[i-1][1];
		g[i][0]=((a[i]-a[i-1]-1)>>1)*g[i-1][1]+((a[i]-a[i-1])>>1)*g[i-1][0];
	}cout << g[m][1]+g[m][0] << endl;
	return 0;
}

Description
When Farmer John isn't milking cows, stacking haybales, lining up his cows, or building fences, he enjoys sitting down with a good book. Over the years, he has collected N books (1 <= N <= 2,000), and he wants to build a new set of bookshelves to hold them all.

Each book i has a width W(i) and height H(i). The books need to be added to a set of shelves in order; for example, the first shelf should contain books 1...k for some k, the second shelf should start with book k+1, and so on. Each shelf can have a total width of at most L (1 <= L <= 1,000,000,000). The height of a shelf is equal to the height of the tallest book on that shelf, and the height of the entire set of bookshelves is the sum of the heights of all the individual shelves, since they are all stacked vertically.

Please help FJ compute the minimum possible height for the entire set of bookshelves.
Input
* Line 1: Two space-separated integers: N and L.

* Lines 2..1+N: Line i+1 contains two space-separated integers: H(i) and W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Output
* Line 1: The minimum possible total height for the set of bookshelves.
Sample Input
5 10
5 7
9 2
8 5
13 2
3 8

INPUT DETAILS:

There are 5 books. Each shelf can have total width at most 10.
Sample Output
21

OUTPUT DETAILS:

There are 3 shelves, the first containing just book 1 (height 5, width 7), the second containing books 2..4 (height 13, width 9), and the third containing book 5 (height 3, width 8).

【Silver难度】：N<=2000

很容易就看出DP了。

令C[i]表示放到第i本书的最小代价。

很明显C[i] = min{max{H[j+1..i]} + C[j]}。(sigma{L[j+1..i]}<=L,0<=j<i)。

那么O(N^2)这道题就过了。

【Gold难度】：N<=100000

目前已被虐傻

二分+后缀自动机还是比较好想的。dp优化只能膜拜题解了。==

题意：给定一些01字符串作为标准作文库。然后给你几篇作文。对于每篇作文，把这篇作文分成若干段后，如果一段的长度不小于L，且是标准作文库中某个字符串的连续子串，这样这一段作文就是匹配的。求L的最大值，使得这篇作文的90%是匹配的。

一眼看出是二分+判定。因为如果L0可行，那小于L0的L都可行。

然后就可以考虑如何判定。分段的话应该是要dp了。设这个作文是S。

先预处理出一个数组d[i],d[i]=max{i-j+1|S[j..i]是标准作文库中某个字符串的连续子串}

这个用后缀自动机。把标准作文库里的所有字符串拼起来。中间加一个分隔符2好了。然后O(n)建后缀自动机。

然后让S在自动机上跑。

跑的过程具体就是：从root开始，如果下一个字符可以转移就转移，更新len值，如果不能就一直回退直到可以转移，回到根了那len=0，如果还没到根，len=当前结点的l值，并且继续转移。

定义数组f[i]为S[1..i]匹配的最大长度。则f[i]=max{f[j]+i-j|i-d[i]<=j<=i-L}。可惜这样dp是O(n^2)的承受不起。

优化：

f[i]=i+max{f[j]-j|i-d[i]<=j<=i-L}。然后令g[j]=f[j]-j。

考虑它的决策区间。

首先i-d[i]是非严格递增的。

如果有某个i，使得i-d[i]>i+1-d[i+1]，由d[i]的意义知S[i-d[i]+1..i]和S[i+1-d[i+1]+1..i+1]是字典中某个串的子串。
由于i-d[i]+1>i+1-d[i+1]+1，知S[i+1-d[i+1]+1..i]也是字典中某个串的子串且比S[i-d[i]+1..i]更长，这与d[i]的定义中的max违背。

i-L是严格递增的。显然。

那么[i-d[i],i-L]只会右移。那么用g[]递减的一个单调队列维护决策区间即可。

最后的复杂度应该是O(nlogn)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1100010;
int l[maxn],ch[maxn][3],d[maxn],f[maxn],g[maxn],q[maxn],fa[maxn];
int rt=1,tail=1,tot=1,n,len;    char s[maxn];
void add(int c){
    int p=tail,np=++tot,r,q;
    l[np]=l[p]+1;   tail=np;
    for(;p&&!ch[p][c];p=fa[p])  ch[p][c]=np;
    if(!p){ fa[np]=rt;  return;}
    if(l[p]+1==l[q=ch[p][c]]){  fa[np]=q;   return;}
    fa[r=++tot]=fa[q];  memcpy(ch[r],ch[q],sizeof(ch[r]));
    l[r]=l[p]+1;    fa[np]=fa[q]=r;
    for(;p&&ch[p][c]==q;p=fa[p])    ch[p][c]=r;
}void init(){
    int p=rt,k=0,x;
    for(int i=1;i<=n;i++){
        if(ch[p][x=s[i]-48])    k++,    p=ch[p][x]; else{
            while(p&&!ch[p][x]) p=fa[p];
            if(!p)  p=rt,k=0;   else    k=l[p]+1,p=ch[p][x];
        }d[i]=k;
    }
}int mt(int r){
    int s=1,e=0,t;
    for(int i=1;i<=n;i++){
        if((t=i-r)>=0){
            while(s<=e&&g[q[e]]<g[t])   e--;
            q[++e]=t;
        }while(s<=e&&q[s]<i-d[i])    s++;
        f[i]=f[i-1];
        if(s<=e&&f[i]<g[q[s]]+i)    f[i]=g[q[s]]+i;
        g[i]=f[i]-i;
    }return f[n]>=len;
}int main(){
    int tc,m;   scanf("%d%d",&tc,&m);
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        int k=strlen(s+1);
        for(int j=1;j<=k;j++)    add(s[j]-48);
        if(i!=m)add(2);
    }while(tc--){
        scanf("%s",s+1);    n=strlen(s+1);
        len=(int)(ceil((double)n*0.9));
        init(); if(!mt(1)){   printf("0\n");  continue;}
        int L=2,R=n,mid;
        while(L<=R){
            mid=(L+R)>>1;
            if(mt(mid)) L=mid+1;    else    R=mid-1;
        }printf("%d\n",R);
    }return 0;
} 

只是来除个草。。

这和当年CH上某cf赛制的题的B题很像。不过是这个的弱化版。

令f[i]表示第i个上面建仓库，1~i的都处理好了之后的最小花费。

那么f[i]=min{f[j]+w(j,i)}+c[i]

然后把w(j,i)化开：=p[j]*(x[i]-x[j])+p[j+1]*(x[i]-x[j+1])+...+p[i]*(x[i]-x[i])

=x[i]*p[j..i]-p[j]*x[j]+p[j+1]*x[j+1]+...+p[i]*x[i]

很明显前后两项都可以用前缀和数组O(1)出来。sp[i]=p[1..i],spx[i]=p[1]*x[1]+..+p[i]*x[i]

可惜这样还是n^2的。n还是100w这么凶残。

那么考虑斜率优化。

把w(j,i)带进去。

f[i]=min{f[j]+x[i](sp[i]-sp[j])-spx[i]+spx[j]}+c[i];

可以发现决策有单调性，x=sp[i]-sp[j],y=f[j]-spx[i]+spx[j],k=x[i]。那么就行了。O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double D;
const int maxn=1000005;
const double inf=1e30;
ll x[maxn],p[maxn],c[maxn],sp[maxn],spx[maxn],q[maxn],f[maxn];
inline D slope(int i,int j){
    ll dx=sp[i]-sp[j],dy=f[i]-f[j]+spx[i]-spx[j];
    if(!dx) return (dy>=0)?inf:-inf;
    return (D)dy/(D)dx;
}inline void read(ll &x){
    ll r=0,f=1;char ch;
    for(ch=getchar();(ch!='-')&&(ch<'0'||ch>'9');ch=getchar());
    if(ch=='-') f=-1; else r=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())r=r*10+ch-48;
    x=r*f;
}int main(){
    ll n;read(n);
    for(ll i=1;i<=n;i++){
        read(x[i]);read(p[i]);read(c[i]);
        sp[i]=sp[i-1]+p[i];
        spx[i]=spx[i-1]+p[i]*x[i];
    }ll s=0,e=0;q[0]=0;
    for(ll i=1;i<=n;i++){
        while(s<e&&slope(q[s],q[s+1])<=(D)x[i])s++;
        f[i]=f[q[s]]+x[i]*(sp[i]-sp[q[s]])-(spx[i]-spx[q[s]])+c[i];
        while(s<e&&slope(q[e],q[e-1])>=slope(i,q[e]))e--;
        q[++e]=i;
    }printf("%lld\n",f[n]);
    return 0;
}

10000个数。有些数空着给你填。每个数的范围都在1~K内。求出填满后的逆序对的最小值。

很明显这几个填的数是递增的。不然自己就产生逆序对了。（没证明过

先处理出da[i][j]表示i~n中比j大的数，xi[i][j]表示1~i中比j小的数。

f[i][j]表示填到第i个数了，这位填了j所产生的逆序对。

则f[i][j]=min{f[i][k]+da[pos[i]][j]+xi[pos[i]][j]}。然后再加上数列本身的逆序对数就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1061109567;
int a[10005],da[10005][105],xi[10005][105],p[10005],f[10005][100],n,k,m=0,An=0;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!~a[i]) p[++m]=i;
    }for(int i=2;i<=n;i++){
        for(int j=1;j<=k;j++) da[i][j]=da[i-1][j];
        if(~a[i-1]) for(int j=1;j<a[i-1];j++) da[i][j]++;
    }for(int i=n-1;i;i--){
        for(int j=1;j<=k;j++) xi[i][j]=xi[i+1][j];
        if(~a[i+1]) for(int j=a[i+1]+1;j<=k;j++) xi[i][j]++;
    }for(int i=1;i<=n;i++) if(~a[i]) An+=da[i][a[i]];
    memset(f,63,sizeof(f));
    for(int i=1;i<=k;i++) f[1][i]=da[p[1]][i]+xi[p[1]][i];
    for(int i=2;i<=m;i++) for(int j=1;j<=k;j++) for(int o=1;o<=j;o++)
        f[i][j]=min(f[i][j],f[i-1][o]+da[p[i]][j]+xi[p[i]][j]);
    int An2=inf;  for(int i=1;i<=k;i++) An2=min(An2,f[m][i]);
    An2=(An2==inf)?0:An2;
    printf("%d\n",An+An2); return 0;
}

设dp[i][j]表示第i个数变为j的最小代价。

则dp[i][j]=min{dp[i-1][k]+c*abs(j-k)+(j-h[i])^2}（k是第i-1位上的数，j是当前位上的数）

100000*100*100。。哗~萎掉了。。

把abs(j-k)拆开试试？

j>k时：dp[i][j]=min{dp[i-1][k]+c*j-c*k+(j-h[i])^2}=min{dp[i-1][k]-c*k}+c*j+(j-h[i])^2

j<k时：dp[i][j]=min{dp[i-1][k]+c*k-c*j+(j-h[i])^2}=min{dp[i-1][k]+c*k}-c*j+(j-h[i])^2

那么我们只要在每次转移的时候记录f数组表示min{dp[i-1][k]-c*k}，g数组表示min{dp[i-1][k]+c*k}。这样转移的时候就是O(10w*100)了~

至于空间的话，第一维好像一点用都没有。那就不要了！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define abs(x) (((x)<0)?(-(x)):(x))
#define sqr(x) ((x)*(x))
int dp[105],f[105],g[105],h[100005],n,c;
const int inf=1061109567;
char buf[2000000],*p=buf;
inline int getint(){
    int r=0;while(*p<48||*p>57)p++;while(*p>47&&*p<58)r=r*10+*p++-'0';return r;
}int main(){
    fread(buf,1,2000000,stdin); n=getint(),c=getint();
    for(int i=1;i<=n;i++) h[i]=getint();
    memset(dp,63,sizeof(dp));
    for(int i=h[1];i<=100;i++) dp[i]=sqr(i-h[1]);
    for(int i=2;i<=n;i++){
        f[101]=inf; for(int j=100;j>=1;j--) f[j]=min(dp[j]+j*c,f[j+1]);
        g[0]=inf;   for(int j=1;j<=100;j++) g[j]=min(dp[j]-j*c,g[j-1]);
        memset(dp,63,sizeof(dp));
        for(int j=h[i];j<=100;j++) dp[j]=sqr(j-h[i])+min(g[j]+j*c,f[j]-j*c);
    }int An=inf;
    for(int i=1;i<=100;i++) An=min(An,dp[i]);
    printf("%d\n",An);  return 0;
}

排序、然后在上下3个中选、dp就好

然后我顺便学了写fread、真好、又快又实用又好写

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll inf=10000000000009LL;
#define abs(x) (((x)<0)?(-(x)):(x))
#define A(x,y) ((x==y)?inf:abs((x)-(y)))
ll n,a[100005],b[100005],f[100005];
char buf[2000000],*p=buf;
inline int getint(){
    ll r=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')r=r*10+*p++-48;return r;
}int main(){
    fread(p,1,2000000,stdin);
    n=getint(); for(ll i=1;i<=n;i++)a[i]=getint(),b[i]=getint();
    sort(a+1,a+n+1);    sort(b+1,b+n+1);
    f[1]=A(a[1],b[1]);  f[2]=min(f[1]+A(a[2],b[2]),A(a[1],b[2])+A(a[2],b[1]));
    for(ll i=3;i<=n;i++)f[i]=min(f[i-1]+A(a[i],b[i]),min(f[i-2]+A(a[i-1],b[i])+A(a[i],b[i-1]),min(f[i-3]+A(a[i],b[i-1])+A(a[i-1],b[i-2])+A(a[i-2],b[i]),f[i-3]+A(a[i],b[i-2])+A(a[i-1],b[i])+A(a[i-2],b[i-1]))));
    printf("%lld\n",f[n]==inf?-1LL:f[n]);    return 0;
}

弱弱的dp我也会做！哈哈哈

设f[i][j]表示高度为i时，在第j个树上能吃到的果子数的最大值。m[i]表示高度为i时吃到的果子数的最大值。w[i][j]表示高度为i，第j颗树上的果子树。

那么方程显而易见：f[i][j]=max(f[i+1][j],m[i+d])+w[i][j]。

读入文件好像奇大、好可怕、话说一开始MLE了、、囧不得不开short、、

orz读入优化、瞬间提升5s、

#include<cstdio>
#define max(a,b) (((a)<(b))?(b):(a))
int n,h,d,k,t,i,j,f[5005][5005]={0},m[5005]={0};    short a[5005][5005]={0};
inline void read(int &x){
    char ch;    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    x=ch-'0';   for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}int main(){
    for(read(n),read(h),read(d),i=1;i<=n;i++)for(read(t),j=1;j<=t;j++)read(k),a[i][k]++;
    for(i=h;~i;i--){
        if(i+d<=h)  t=m[i+d];   else    t=0;
        for(j=1;j<=n;j++)   f[i][j]=max(f[i+1][j],t)+a[j][i],   m[i]=max(m[i],f[i][j]);
    }printf("%d",m[0]); return 0;
}