DZY 's BLOG

题意：给你一个字符串。每次取出第一个字符或最后一个字符，放到新的字符串（初始为空）后面。求最小字典序的新字符串。

比如样例：ACDBCB。按这样的顺序拿：头尾尾尾头尾。这样得到ABCBCD。可以证明没有比它字典序更小的了。

一开始我先YY了个很傻比的贪心。第一个字符和最后一个字符比较。取小的。然后O(n)扫一遍。（画外音：你煞笔啊、gold的题目就给你这么水掉啊！、、）本着这种态度很快就发现样例都过不了。先取出A、B。然后是取队头的C还是队尾的C呢。这时就发现光比较这一个字符的大小是不够的。要比较整个字符串和整个字符串反转过来的字符串的字典序大小，才能决定取哪个。

那么想到了什么呢？很明显就是后缀数组。

把这个字符串反转一遍接在原字符串后面，中间加一个分隔符（最好是小于'A'的，比如'@'）。然后求出rank数组。

下标  0  1 2 3  4 5 6  7 8  9 10 11 12

字符  A C D B C B @ B C B D  C   A

那么维护两个指针，一个从0开始，一个从n+1（反转的字符串的起点）开始。比较rank的大小，每次取小的先输出。OK！

（fread、fwrite蛮好的、轻松rank3）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100000;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],sa[maxn],str[maxn];
char s[maxn],buf[maxn],*p=buf,buf2[maxn],*o=buf2;
inline bool cmp(int *r,int a,int b,int l){
    return  r[a]==r[b] && r[a+l]==r[b+l];
}inline void da(char *r,int *sa,int n,int m){
    int i,j,p,*x=tmp1,*y=tmp2,*t;
    for(i=0;i<m;i++)cs[i]=0;
    for(i=0;i<n;i++)cs[x[i]=r[i]]++;
    for(i=1;i<m;i++)cs[i]+=cs[i-1];
    for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,m=p){
        for(p=0,i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<n;i++)cv[i]=x[y[i]];
        for(i=0;i<m;i++)cs[i]=0;
        for(i=0;i<n;i++)cs[cv[i]]++;
        for(i=1;i<m;i++)cs[i]+=cs[i-1];
        for(i=n-1;i>=0;i--)sa[--cs[cv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }for(i=0;i<n;i++)rank[sa[i]]=i;
}int main(){
    fread(p,1,maxn,stdin);  int t=0,n=0;
    while(*p<'0'||*p>'9')p++;
    while(*p>='0'&&*p<='9')n=n*10+*p++-48;
    for(int i=1;i<=n;i++){ 
        while(*p<'A'||*p>'Z')p++;
        s[t++]=*p++; 
    }s[t++]='A'-1;
    for(int i=n-1;~i;i--)   s[t++]=s[i];    s[t++]='\0';
    da(s,sa,t,256);
    int j=0,k=n+1,c=0;
    for(int i=1;i<=n;i++)str[c++]=rank[j]>rank[k]?k++:j++;
    for(int i=0;i<n;i++){
        if(i&&i%80==0)*o++='\n';
        *o++=s[str[i]];
    }fwrite(buf2,1,o-buf2,stdout);
    return 0;
}

题意：修改区间内的数、询问区间内任意子段和的期望值。

然后我们尝试把每次的答案求出来。然后对这个式子乱搞。发现对于每个数a[i]，维护a[i],i*a[i],i*i*a[i]就好了、

那么线段树维护就行了。好了没了。（其实是我懒得写题解了、、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson l,mid,ls
#define rson mid+1,r,rs
#define root 1,n,1
typedef long long ll;
const int maxn=500005;
ll a[maxn]={0},b[maxn]={0},c[maxn]={0},add[maxn]={0};
char buf[5000000],*pt=buf,buf2[5000000],*o=buf2;
inline ll getint(){
    ll r=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++; if(*pt=='-')f=-1, pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;   return r*f;
}inline char getop(){
    while(*pt!='C'&&*pt!='Q')pt++;  return *pt;
}inline void print(ll x){
    char str[30],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}inline void pushup(ll rt){
    a[rt]=a[ls]+a[rs], b[rt]=b[ls]+b[rs], c[rt]=c[ls]+c[rs];
}inline void pushdown(ll l,ll r,ll rt){
    ll lc=mid-l+1, rc=r-mid, rr=mid, ll=mid+1;  
    if(add[rt]){
        add[ls]+=add[rt];
        a[ls]+=lc*add[rt];
        b[ls]+=(l+rr)*lc*add[rt]>>1;
        c[ls]+=(rr*(rr+1)*(rr<<1|1)-(l-1)*l*(l-1<<1|1))/6*add[rt];
        add[rs]+=add[rt];
        a[rs]+=rc*add[rt];
        b[rs]+=(ll+r)*rc*add[rt]>>1;
        c[rs]+=(r*(r+1)*(r<<1|1)-(ll-1)*ll*(ll-1<<1|1))/6*add[rt];
        add[rt]=0;
    }
}void update(ll L,ll R,ll d,ll l,ll r,ll rt){
    if(L<=l&&r<=R){
        add[rt]+=d;
        a[rt]+=(r-l+1)*d;
        b[rt]+=(l+r)*(r-l+1)*d>>1;
        c[rt]+=(r*(r+1)*(r<<1|1)-(l-1)*l*(l-1<<1|1))/6*d;
        return;
    }pushdown(l,r,rt);
    if(L<=mid)  update(L,R,d,lson);
    if(mid<R)   update(L,R,d,rson);
    pushup(rt);
}void query(ll L,ll R,ll&A,ll&B,ll&C,ll l,ll r,ll rt){
    if(L<=l && r<=R){
        A=a[rt],B=b[rt],C=c[rt]; return;
    }pushdown(l,r,rt);
    ll SA=0,SB=0,SC=0,TA,TB,TC;
    if(L<=mid)  query(L,R,TA,TB,TC,lson), SA+=TA, SB+=TB, SC+=TC;
    if(mid<R)   query(L,R,TA,TB,TC,rson), SA+=TA, SB+=TB, SC+=TC;
    A=SA,B=SB,C=SC;
}inline ll gcd(ll a,ll b){
    return (!b)?a:gcd(b,a%b);
}int main(){ 
    fread(pt,1,5000000,stdin);  ll n,q,u,v,w,TA,TB,TC,A,B,C;
    for(n=getint(),q=getint();q;q--){
        if(getop()=='C'){
            u=getint(),v=getint(),w=getint();
            update(u,v-1,w,root);
        }else{
            u=getint(),v=getint();
            query(u,v-1,TA,TB,TC,root);
            A=(u+v-1)*TB+TA*(v-v*u)-TC;
            B=(v-u+1)*(v-u)>>1;
            C=gcd(A,B);
            print(A/C);*o++='/';print(B/C);*o++='\n';
        }
    }fwrite(buf2,1,o-buf2,stdout);return 0;
}

原来省选题也有裸背包啊、、

if (F[i-1][j]) then F[i][j+c[i]]=F[i][j-c[i]]=1

好了水掉了

#include<cstdio>
int f[52][1005]={0},n,st,ed,c[52];
int main(){
    scanf("%d%d%d",&n,&st,&ed); for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    f[0][st]=1;  for(int i=1;i<=n;i++)   for(int j=0;j<=ed;j++){
        if(!f[i-1][j])  continue;
        if(j+c[i]<=ed)  f[i][j+c[i]]=1;
        if(j-c[i]>=0)   f[i][j-c[i]]=1;
    }int An;    for(An=ed;~An;An--) if(f[n][An]) break; printf("%d\n",An);
}

自己YY出来了？估计应该是比较简单的网络流入门题吧。。

既然每个点(i,j)最多只能通过c[i][j]个蜥蜴。那么很自然地想到拆点。(i,j)→(i,j)'连上容量为c[i][j]的边。(i,j)为入点。(i,j)'为出点。

对于所有有蜥蜴的点，从S给它连一条容量为1的边。对于所有可以跳到外面的点，连到T，容量是c[i][j]。

然后n^4枚举在内部跳来跳去的情况。最后跑网络流就好了。

连T的边的时候我一直在傻×、、一开始算的是到(0,0)的距离≤d、、果然还是太弱了哎、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000,maxm=500000,inf=1000000009;
int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn],id[25][25];
int S,T,n,m,k,tot=0,cnt=0,N=0;    char s[25];
inline void ae(int x,int y,int z){
    p[tot]=y;   c[tot]=z;   n1[tot]=h[x];   h[x]=tot++;
    p[tot]=x;   c[tot]=0;   n1[tot]=h[y];   h[y]=tot++;
}inline int bfs(){
    memset(d,0xff,sizeof(d));   int r=d[q[0]=S]=0;
    for(int l=0;l<=r;l++)
        for(int k=h[q[l]];~k;k=n1[k])
            if(c[k] && !~d[p[k]])   d[q[++r]=p[k]]=d[q[l]]+1;
    return ~d[T];
}int dfs(int x=S,int lmt=inf){
    if(x==T)    return lmt; int flow;
    for(int &k=g[x];~k;k=n1[k]){
        if(c[k] && d[p[k]]==d[x]+1 && (flow=dfs(p[k],min(lmt,c[k])))){
            c[k]-=flow; c[k^1]+=flow;   return flow;
        }
    }return 0;
}int main(){
    scanf("%d%d%d",&n,&m,&k);   k;   S=0;    T=801;  memset(h,0xff,sizeof(h));
    for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++)   if(s[j]-'0'){
        id[i][j]=++cnt;
        ae((id[i][j]<<1)-1,id[i][j]<<1,s[j]-'0');
        if(min(min(i,n-i+1),min(j,m-j+1))<=k)ae(id[i][j]<<1,T,s[j]-'0');
    }for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int ii=1;ii<=n;ii++) for(int jj=1;jj<=m;jj++){
        if(!id[i][j]||!id[ii][jj])  continue;
        if((ii-i)*(ii-i)+(jj-j)*(jj-j)<=k*k)  ae(id[i][j]<<1,(id[ii][jj]<<1)-1,inf);
    }for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++) if(s[j]=='L'){
        N++; if(id[i][j])   ae(S,(id[i][j]<<1)-1,1);
    }int An=0,f=0;   while(bfs()){   memcpy(g,h,sizeof(h));  while(f=dfs())  An+=f;}
    printf("%d\n",N-An);    return 0;
} 

【吐槽：我不想保护出题人。。。】

首先把读入的a数组变成前缀和。然后就可以发现y数组其实就是这个东西这就是确保杀死j~i(j≤i)这一段僵尸的最小速度。伤害的和是a[i]-a[j-1]，第j个~第i个之间的距离是di-dj，还要加上x[i]才是与家的距离。很绕吗？自己脑补吧。。

观察这个式子比较像求直线的斜率。那么我们把它转化为两点之间的斜率好了。把跟i有关的看成一个点，跟j有关的看成一个点。

那么就是(x[i]+d*i,a[i])和(d*j,a[j-1])两个点。然后只要求斜率了！！！

那么用单调栈维护一个凸壳就好了！！！计算斜率的时候二分。二分的时候先判是不是在凸壳的外部，然后取栈里面最上面那个就好了。

很好。nlogn了。

这是样例，有线连着的点是转化过的(d*j,a[j-1])。其中虚线是最后形成的凸壳。

查询第i次的时候就是先转化为(x[i]+d*i,a[i])这个点，然后二分凸壳上的点求最大的斜率就好。

比如查询第一次。凸壳（黄线）中只有(2,0)这个点。要查询的是(5,3)。很明显斜率只能是1。

查询第二次。查询的点是(5,4)。凸壳中有两个点(2,0)，(4,3)。选前者的算出的斜率1.3333比后者的1要优。

然后以此类推就可以解决全部询问。

这道题在八中上rank1了我会告诉你们？介于是rank1我就不发rank1的代码了、、这个是目前rank10的、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double D; D a[100005],x[100005],d,An=0;
struct P{D x,y;P(){};P(D _x,D _y):x(_x),y(_y){};}p[100005];
D cross(P a,P b,P c){ return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);}
int st[100005],top=0,n;
int main(){
    scanf("%d%lf",&n,&d);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i],&x[i]);
        a[i]+=(p[i].y=a[i-1]);  p[i].x=i*d;
    }for(int i=1;i<=n;i++){
        while(top&&cross(p[st[top]],p[i],p[st[top-1]])<0)top--;
        st[++top]=i;     P s(x[i]+i*d,a[i]);
        int j=1,l=1,r=top,mid;  while(l<=r){
            mid=l+r>>1;
            if(cross(p[st[mid]],p[st[mid-1]],s)<0)j=max(j,mid),l=mid+1;else r=mid-1;
        }An+=(s.y-p[st[j]].y)/(s.x-p[st[j]].x);
    }printf("%.0lf\n",An);  return 0;
}

第一问先求1到n的最短路。第二问求破坏一些路使得1到n的最短路变大。每条路被破坏都要花费一定的代价Ci。求min∑Ci。

我学会了写spfa好开心啊！我学会了写dinic好开心啊！==

破坏边使不连通明显最小割水掉嘛、、

好了言归正传、先求出所有的最短路。然后判断每条边是不是在1~n的最短路上。是的话就连边。然后再新建的图上做最小割。

一开始建图建错了、、应该这么建：首先以1为源点跑spfa，记录d[0][i]为1~i的最短路。然后以n为源点跑spfa，记录d[1][i]为n~i的最短路。

如果i在1~n的最短路上那一定满足d[0][i]+d[1][i]==d[0][n]（这也是第一问的答案、、）且d[0][i]+w(i,j)=d[0][j]。

然后就没了、、继续fread然后刷到rank5、、、

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxm=250000,maxn=505,inf=2000000009;
struct edge{int t,c,next;}E[maxm];
char buf[3000000],*pt=buf;
int p[maxm],w[maxm],c[maxm],n1[maxm],h[maxn],v[maxn],d[2][maxn],q[maxm],V[maxn],level[maxn],n,m,tot=0,tt=0,S,T,An=inf;
inline int getint(){
    int r=0; while(*pt<'0'||*pt>'9')pt++; while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void ae1(int u,int v,int t,int cc){
    p[tot]=v;   w[tot]=t;   c[tot]=cc;  n1[tot]=h[u];   h[u]=tot++;
    p[tot]=u;   w[tot]=t;   c[tot]=cc;  n1[tot]=h[v];   h[v]=tot++;
}inline void ae2(int a,int b,int c){
    E[tt].t=b; E[tt].c=c; E[tt].next=V[a];   V[a]=tt++;
    E[tt].t=a; E[tt].c=0; E[tt].next=V[b];   V[b]=tt++;
}inline int bfs(){
    memset(level,0xff,sizeof(level));   int head=0,tail=1;  q[0]=S; level[S]=1;
    while(head<tail){
        int u=q[head++];    if(u==T)return 1;
        for(int p=V[u];p!=-1;p=E[p].next)
            if(E[p].c>0 && level[E[p].t]==-1) level[E[p].t]=level[u]+1,q[tail++]=E[p].t;
    }return 0;
}int dfs(int u=S,int lmt=inf){
    if(u==T)    return lmt; int ret=0,  delta;
    for(int p=V[u];p!=-1;p=E[p].next){
        if(E[p].c>0 && level[E[p].t]==level[u]+1){
            delta=dfs(E[p].t,min(lmt-ret,E[p].c));
            E[p].c-=delta;  E[p^1].c+=delta;    ret+=delta;
            if(ret==lmt)    return ret;
        }
    }if(!ret)   level[u]=-1;    return ret;
}inline int dinic(){
    int ret=0;S=1,T=n;
    for(int i=1;i<=n;i++)for(int j=h[i];~j;j=n1[j])
        if(d[0][p[j]]+d[1][p[j]]==An && d[0][i]+w[j]==d[0][p[j]]) ae2(i,p[j],c[j]);
    while(bfs())ret+=dfs(); return ret;
}inline void spfa(int SS,int f){
    for(int i=1;i<=n;i++)d[f][i]=inf; memset(v,0,sizeof(v));
    int head=0,tail=1;  q[0]=SS; v[SS]=1; d[f][SS]=0;
    while(head<tail){
        int u=q[head++];    v[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(d[f][u]+w[i]<d[f][p[i]]){
                d[f][p[i]]=d[f][u]+w[i];  if(!v[p[i]])  v[p[i]]=1,  q[tail++]=p[i];
            }
    }
}int main(){
    fread(pt,1,3000000,stdin);  n=getint(),m=getint();  memset(h,-1,sizeof(h)); memset(V,-1,sizeof(V));
    for(int u,v,t,c,i=1;i<=m;u=getint(),v=getint(),t=getint(),c=getint(),ae1(u,v,t,c),i++);
    spfa(1,0);  spfa(n,1);  for(int i=1;i<=n;i++)   An=min(An,d[0][i]+d[1][i]);
    printf("%d\n%d\n",An,dinic()); return 0;
}

果然是3越多越好、、滚回去学小学奥数算了、、、

然后就是高精度了、、比较脑残选择了手写、、更加脑残的选择了压位和快速幂、、然后跑的还行、、

代码越写越短了、、不过还有更短的比不过、、呵呵、、、

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Hugeint{
    ll len,num[10000];  Hugeint(){  len=1ll;  memset(num,0,sizeof(num));}
}An;ll n,two,thr,p[]={1,10,100,1000};
Hugeint Mul(Hugeint a,Hugeint b){
    Hugeint c;  c.len=a.len+b.len+1;
    for(ll i=1;i<=a.len;i++) for(ll j=1;j<=b.len;j++)  c.num[i+j-1]+=a.num[i]*b.num[j];
    for(ll i=1;i<c.len;i++)  if(c.num[i]>9999)  c.num[i+1]+=c.num[i]/10000,  c.num[i]%=10000;
    while(c.num[c.len]>9999) c.len++,  c.num[c.len]+=c.num[c.len-1]/10000,   c.num[c.len-1]%=10000;
    while(c.num[c.len]==0&&c.len>1)  c.len--;   return c;
}Hugeint pow(ll b,ll p){
    Hugeint ans,bb; ans.len=bb.len=ans.num[1]=1ll;  bb.num[1]=b;
    while(p){if(p&1ll)ans=Mul(ans,bb);p>>=1ll;bb=Mul(bb,bb);}   return ans;
}inline int len(int x){
    int r=0; while(x)r++,x/=10; return r;
}void print(Hugeint a){
    if(a.len<=25){ printf("%lld",a.num[a.len]); for(ll i=a.len-1;i;i--)printf("%04lld",a.num[i]); return;} 
    printf("%lld",a.num[a.len]);    for(ll i=a.len-1;i>=a.len-24;i--)printf("%04lld",a.num[i]);
    if(len(a.num[a.len])<4) printf("%lld\n",a.num[a.len-25]/p[len(a.num[a.len])]);
}int main(){
    scanf("%lld",&n); two=0,thr=n/3;  if(n%3)two=2/(n%3),thr=(n-4/(n%3))/3; An=Mul(pow(2,two),pow(3,thr));
    printf("%lld\n",(An.len-1<<2)+len(An.num[An.len])); print(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这一段最少要涂几次。每次递归计算、头尾如果相同可以最先涂、所以可以减1、然后合并上来就行、、

最近写的代码怎么都这么短？还是我太弱了只会刷水？唉、、囧、、、

#include<cstdio>
#include<algorithm>
#include<cstring>
const int inf=1000000009;
int F[60][60]={0},l;    char s[60];
int f(int l,int r){
    if(l==r)    return 1;   if(F[l][r]) return F[l][r]; F[l][r]=inf;
    for(int i=l;i<=r;i++)   F[l][r]=std::min(f(l,r),f(l,i)+f(i+1,r));
    return F[l][r]-=(s[l]==s[r]);
}int main(){
    scanf("%s",s);  l=strlen(s);    printf("%d\n",f(0,l-1));   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;
}