首页 > > 程序设计 > C/C++ >

day20

2019-08-26 05:36:52来源：博客园阅读 ()

day20

洛谷说的可真准！，T1T3爆0；

T1疑似因为复杂度过高全T，T3垃圾题面；

T2暴力得了20；

总得分20/300自闭ing

T1递推

#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
struct node{
    long long a,b;
}e[1010][1010];
long long f[1010*1010];
int n,m,tot,bef[1010*1010];
long long ans;
inline int read()
{
    int x=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x;
}
struct travel
{
    int x,y,hgd;
}dian[1010*1010+1];
inline int abs(int x){return x>0?x:-x;}
inline long long manhadun(long long i,long long j){return 1LL*abs(dian[i].x-dian[j].x)+1LL*abs(dian[i].y-dian[j].y);}
inline int cmp(travel a,travel b){return a.hgd<b.hgd;}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    e[i][j].a=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        e[i][j].b=read();
        if(!e[i][j].a&&!e[i][j].b)continue;
        dian[++tot].x=i;
        dian[tot].y=j;
        dian[tot].hgd=e[i][j].a;
    }
    sort(dian+1,dian+1+tot,cmp);
    for(int i=1;i<=tot;i++)
    {
        int j=max(bef[i-1],1);
        for(;j<i;j++)
        {
            if(dian[i].hgd>dian[j].hgd)
            {
                if(f[i]<f[j]+manhadun(i,j))
                {
                    f[i]=f[j]+manhadun(i,j);
                    bef[i]=j;
                }
            }
        }
        f[i]=f[i]+1LL*e[dian[i].x][dian[i].y].b;
        ans=ans>f[i]?ans:f[i];
    }
    cout<<ans<<endl;
    return 0;
}

View Code

解释不了，全靠自己理解了

T2卡特兰数+递推+矩乘优化

#include<bits/stdc++.h>
#define MOD 1000000007LL
#define oyy main
using namespace std;
int n,m;
struct node{
    long long a[110][110];
}ans,f,dt;
inline void X(node x,node y)
{
    memset(ans.a,0,sizeof(ans.a));
    for(int i=1;i<=m/2;i++)
        for(int j=1;j<=m/2;j++)
            for(int k=1;k<=m/2;k++)
                ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
}
inline void ksm(int x)
{
    if(!x)return;
    if(x%2==1)ksm(x-1);else ksm(x/2);
    if(x%2==1)X(ans,f);else X(ans,ans);
}
int oyy()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    dt.a[1][1]=1;
    for(int i=1;i<m;i++)
        for(int j=1;j<=m/2;j++)
            if(dt.a[i][j])
            {
                dt.a[i+1][j+1]=(dt.a[i][j]+dt.a[i+1][j+1])%MOD;
                dt.a[i+1][j-1]=(dt.a[i][j]+dt.a[i+1][j-1])%MOD;
            }
    for(int i=1;i<=m/2;i++)f.a[1][i]=(dt.a[i*2][0]*2)%MOD;
    for(int i=2;i<=m/2;i++)f.a[i][i-1]=1;
    for(int i=1;i<=m/2;i++)ans.a[i][i]=1;
    ksm(n/2);
    cout<<ans.a[1][1]<<endl;
    return 0;
}