头像

希冀




离线:5个月前


最近来访(114)
用户头像
zhn0012
用户头像
lzc_Fe_fw
用户头像
why_85
用户头像
Northrain
用户头像
Weather
用户头像
重生之我是闫学灿yxc
用户头像
敲爱笑的晨晨
用户头像
寄一心明月
用户头像
人生如戏ba
用户头像
Cedeat
用户头像
Mup丶Superman
用户头像
no_one
用户头像
_whiz
用户头像
furcat
用户头像
呐呐呐呐
用户头像
jeffstart
用户头像
BT7274
用户头像
栗子ing
用户头像
负暄
用户头像
垫底抽風


希冀
5个月前

打个卡,状态定义想错了,没写出来,记得开n*2

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int f[110][110][20],g[110][110][20],a[110],s[110];
int main()
{
   int n,m;
   cin>>n>>m;
   for(int i=1;i<=n;i++)
   {
       cin>>a[i];a[i+n]=a[i];
   }
   for(int i=1;i<=n*2;i++)
   s[i]=s[i-1]+a[i];
   memset(g,0x3f,sizeof g);
   for(int i=1;i<=n*2;i++)
   for(int j=1;j<=n*2;j++)
   {
       f[i][j][1]=((s[j]-s[i-1])%10+10)%10;
       g[i][j][1]= f[i][j][1];
   }
   for(int len=2;len<=n;len++)
   for(int i=1;i+len-1<=2*n;i++)
   {
       int j=i+len-1;
       for(int k=2;k<=m;k++)
       for(int u=i+k-2;u<j;u++)
        {
          f[i][j][k]=max(f[i][j][k],f[i][u][k-1]*(((s[j]-s[u])%10+10)%10));
          g[i][j][k]=min(g[i][j][k],g[i][u][k-1]*(((s[j]-s[u])%10+10)%10));  
        }
   }
   int minn=0x3f3f3f3f,maxn=0;
   for(int i=1;i<=n;i++)
   {
       minn=min(g[i][i+n-1][m],minn);
       maxn=max(f[i][i+n-1][m],maxn);
   }
   cout<<minn<<endl;
   cout<<maxn<<endl;
    return 0;
}


活动打卡代码 AcWing 1222. 密码脱落

希冀
5个月前
#include<iostream>
#include<algorithm>


using namespace std;

int f[1010][1010];
int main()
{
    string s;
    cin>>s;
    int n=s.size();
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(i==j)
    f[i][j]=1;
    for(int len=2;len<=n;len++)
    for(int i=0;i+len-1<n;i++)
    {
        int j=i+len-1;
        if(s[i]==s[j])
        f[i][j]=max(f[i][j],f[i+1][j-1]+2);
        else
        f[i][j]=max(f[i][j],max(f[i+1][j],f[i][j-1]));
    }
    cout<<n-f[0][n-1];
    return 0;
}


活动打卡代码 AcWing 282. 石子合并

希冀
5个月前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int f[500][500],a[500],s[500];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(i==j) f[i][j]=0;

    for(int len=2;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            for(int k=i;k<j;k++)
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
    }
    cout<<f[1][n];
    return 0;
}


活动打卡代码 AcWing 283. 多边形

希冀
5个月前

目前最后一个数据过不去,破案了,数组开小了,要开两倍,因为环要拆成链

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

long long  f[110][110],a[110],g[110][110];
char b[60][60];
int main()
{
    int n;
    cin>>n;
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n*2;i++)
    {
        if(i%2)
        {
            char s;cin>>s;
            b[cnt1][(cnt1+1)%n]=s;
            b[(cnt1+1)%n][cnt1]=s;
            cnt1++;
        }
        if(i%2==0)
        {
            int t;cin>>t;
            cnt2++;
            a[cnt2]=t;
            a[cnt2+n]=t;
        }
    }

    memset(f,-0x3f,sizeof f);
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=2*n;i++)
    for(int j=1;j<=2*n;j++)
    if(i==j)
    {
        //注意这里和合并石子不一样,不是0,自己思考一下为什么
        f[i][j]=a[i];
        g[i][j]=a[i];
    }
    for(int len=2;len<=2*n;len++)
    for(int i=1;i+len-1<=2*n;i++)
    {
        int j=i+len-1;
        for(int k=i;k<j;k++)
        {
            if(b[k%n][(k+1)%n]=='t')
            {
                //这里和合并石子也不一样,没有加上前缀和信息,自己好好思考一下
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
                g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]);
            }
            else
            {
                long long  minl=g[i][k],minr=g[k+1][j],maxl=f[i][k],maxr=f[k+1][j];
                long long x1=minl*minr,x2=minl*maxr,x3=maxl*minr,x4=maxl*maxr;
                f[i][j]=max(f[i][j],max(max(max(x1,x2),x3),x4));
                g[i][j]=min(g[i][j],min(min(min(x1,x2),x3),x4));
            }
        }
    }
    long long  ans=0;
    for(int i=1;i<=n;i++)
    ans=max(ans,f[i][i+n-1]);
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
    if(f[i][i+n-1]==ans)
    cout<<i<<' ';
    return 0;
}


活动打卡代码 AcWing 273. 分级

希冀
5个月前

算法进阶指南——分级.png

优化暂时想不明白,先贴个朴素做法

朴素做法,复杂度O(n$^3$)

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int f[2010][2010],a[2010],n;
int dp()
{

    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++)
    f[0][i]=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    {
        if(a[k]<=a[j])
        f[i][j]=min(f[i][j],f[i-1][k]+abs(a[j]-a[i]));
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    ans=min(ans,f[n][i]);
    return ans;
}
int main()
{

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int low=dp();
    reverse(a+1,a+1+n);
    int gre=dp();
    cout<<min(low,gre);
    return 0;
}


活动打卡代码 AcWing 312. 乌龟棋

希冀
5个月前
#include<iostream>
#include<algorithm>

using namespace std;

int f[50][50][50][50],b[4],a[400];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    cin>>a[i];
    for(int i=1;i<=m;i++)
    {
       int x;
       cin>>x;
       x--;
       b[x]++;
    }
    f[0][0][0][0]=a[0];
    for(int i=0;i<=b[0];i++)
    for(int j=0;j<=b[1];j++)
    for(int k=0;k<=b[2];k++)
    for(int u=0;u<=b[3];u++)
    {
        int &v= f[i][j][k][u];
        int w=a[i*1+j*2+k*3+u*4];
        if(i>0) v=max(v,f[i-1][j][k][u]+w);
        if(j>0) v=max(v,f[i][j-1][k][u]+w);
        if(k>0) v=max(v,f[i][j][k-1][u]+w);
        if(u>0) v=max(v,f[i][j][k][u-1]+w);
    }
    cout<<f[b[0]][b[1]][b[2]][b[3]];
    return 0;
}


活动打卡代码 AcWing 2023. 连接奶牛

希冀
5个月前

所有方案数等于点的全排列,由于n只有10

dfs即可

#include<iostream>
#include<algorithm>

using namespace std;

struct node{
    int x,y;
}a[15];
int vis[15],n,ans;
//返回从i到j的方向
int  check(int i,int j)
{
    if(a[i].x!=a[j].x&&a[i].y!=a[j].y) return -1;//i,j必须有一个相等
    if(a[i].x==a[j].x)
    {
        if(a[i].y<a[j].y) return 1;
        else return 0;
    }
    if(a[i].y==a[j].y)
    {
        if(a[i].x<a[j].x) return 2;
        else return 3;
    }
}
void dfs(int u,int s,int t)//暴搜,u代表当前点,s代表上一个点,t代表走了几个点
{
    if(t==n)
    {
        if(check(u,0)!=-1&&check(s,u)!=check(u,0))
        ans++;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&check(u,i)!=-1&&check(u,i)!=check(s,u))
        {
            vis[i]=1;
            dfs(i,u,t+1);
            vis[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)
    {
        if(check(i,0)!=-1)
        {
            vis[i]=1;
            dfs(i,0,1);
            vis[i]=0;
        }
    }
    cout<<ans;
    return 0;

}


活动打卡代码 AcWing 4285. 多少张桌子

希冀
5个月前
#include<iostream>
#include<algorithm>

using namespace std;

int p[1010];
int find(int x)
{
    if(x!=p[x])
    p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
         for(int i=1;i<=n;i++)
        p[i]=i;
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            if(find(a)!=find(b))
            {
                p[find(a)]=find(b);
                n--;
            }
        }
        cout<<n<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 4267. 可疑人员

希冀
5个月前

读入很多,要用scanf,不然会T

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
int p[30010],s[30010];
int find(int x)
{
    if(x!=p[x])
    p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    while(cin>>n>>m,n||m)
    {
        for(int i=0;i<=n;i++)
        p[i]=i,s[i]=1;
        while(m--)
        {
            int k,u;
            scanf("%d",&k);
            for(int i=0;i<k;i++)
            {
                int x;scanf("%d",&x);
                if(i==0) u=find(x);
                if(find(x)!=u)
                {
                    s[u]+=s[find(x)];
                    p[find(x)]=u;
                }
            }
        }
        printf("%d",s[find(0)]);
        printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 4266. 无线网络

希冀
5个月前
#include<iostream>
#include<algorithm>

using namespace std;

#define x first
#define y second
typedef pair<int,int> PII;
int vis[1010],n,d,p[1010];
PII a[1010];
bool get(int x1,int y1,int x2,int y2)
{
    if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=d*d)
    return true;
    else return false;
}
int find(int x)
{
    if(x!=p[x])
    p[x]=find(p[x]);
    return p[x];
}
int  main()
{

    cin>>n>>d;
    for(int i=1;i<=n;i++)
    cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)
    p[i]=i;
    char s;
    while(cin>>s)
    {
        if(s=='O')
        {
            int i;
            cin>>i;
            vis[i]=1;
            for(int j=1;j<=n;j++)
            {
                if(vis[j]&&get(a[i].x,a[i].y,a[j].x,a[j].y))
               p[find(i)]=find(j);
            }
        }
        else
        {
            int x,y;
            cin>>x>>y;
            if(find(x)==find(y)) cout<<"SUCCESS"<<endl;
            else cout<<"FAIL"<<endl;
        }
    }
    return 0;
}