3 条题解

  • 1
    @ 2026-11-15 10:28:59
    #include<iostream>
    #include<cstring>
    using namespace std;
    const int maxn=5010;
    int n,ans=1,a[maxn],ans_f[maxn],f[maxn],c[maxn][110];
    bool flag[maxn*4];
    void add(int *x,int *y)
    {
        int t=0,len=1,z[110]={0};
        while(len<=x[0]||len<=y[0])
        {
            z[len]=x[len]+y[len]+t;
            t=z[len]/10;
            z[len]=z[len]%10;
            len++;
        }
        z[len]=t;
        if(!z[len])
        len--;
        x[0]=len;
        for(int i=1;i<=len;i++)
        x[i]=z[i];
    }
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            f[i]=1;
        }
        for(int i=2;i<=n;i++)
          for(int j=1;j<i;j++)
          if(a[j]>a[i])
          {
            f[i]=max(f[i],f[j]+1);
            ans=max(ans,f[i]);
          }
        for(int i=1;i<=n;i++)
        {
            if(f[i]==1)
            {
                c[i][0]=1;
                c[i][1]=1;
            }
            else
            {
                memset(flag,0,sizeof(flag));
                c[i][0]=1;
                for(int j=i-1;j>=1;j--)
                if(f[j]+1==f[i]&&!flag[a[j]]&&a[i]<a[j])
                {
                    add(c[i],c[j]);
                    flag[a[j]]=1;
                }
            }
        }
        memset(flag,0,sizeof(flag));
        for(int i=n;i>=1;i--)
        if(f[i]==ans&&!flag[a[i]])
        {
            add(ans_f,c[i]);
            flag[a[i]]=1;
        }
        cout<<ans<<" ";
        for(int i=ans_f[0];i>=1;i--)
        cout<<ans_f[i];
        return 0;
    }
    
    • 0
      @ 2023-4-24 19:30:54

      有些难度

      #include<iostream>
      #include<cstring>
      using namespace std;
      const int maxn=5010;
      int n,ans=1,a[maxn],ans_f[maxn],f[maxn],c[maxn][110];
      bool flag[maxn*4];
      void add(int *x,int *y)
      {
          int t=0,len=1,z[110]={0};
          while(len<=x[0]||len<=y[0])
          {
              z[len]=x[len]+y[len]+t;
              t=z[len]/10;
              z[len]=z[len]%10;
              len++;
          }
          z[len]=t;
          if(!z[len])
          len--;
          x[0]=len;
          for(int i=1;i<=len;i++)
          x[i]=z[i];
      }
      int main()
      {
          cin>>n;
          for(int i=1;i<=n;i++)
          {
              cin>>a[i];
              f[i]=1;
          }
          for(int i=2;i<=n;i++)
            for(int j=1;j<i;j++)
            if(a[j]>a[i])
            {
              f[i]=max(f[i],f[j]+1);
              ans=max(ans,f[i]);
            }
          for(int i=1;i<=n;i++)
          {
              if(f[i]==1)
              {
                  c[i][0]=1;
                  c[i][1]=1;
              }
              else
              {
                  memset(flag,0,sizeof(flag));
                  c[i][0]=1;
                  for(int j=i-1;j>=1;j--)
                  if(f[j]+1==f[i]&&!flag[a[j]]&&a[i]<a[j])
                  {
                      add(c[i],c[j]);
                      flag[a[j]]=1;
                  }
              }
          }
          memset(flag,0,sizeof(flag));
          for(int i=n;i>=1;i--)
          if(f[i]==ans&&!flag[a[i]])
          {
              add(ans_f,c[i]);
              flag[a[i]]=1;
          }
          cout<<ans<<" ";
          for(int i=ans_f[0];i>=1;i--)
          cout<<ans_f[i];
          return 0;
      }
      
      • -1
        @ 2023-7-19 10:33:29

        注意如果你也像我一样使用__int128就只能特(打)判(表),因为倒数第二个点方案书长达61位,正解得用高精度。不过大多数情况__int128足矣。

        #include 
        #define int	long long
        using namespace std;
        
        const int N = 1e4;
        int n;
        int a[N];
        int dp[N];
        int p[100];
        int ans = 0;
        __int128 f[N];
        
        void print(__int128 x)
        {
            if(x < 0)
        	{
                putchar('-');
                x = -x;
            }
            if(x > 9)
                print(x / 10);
            putchar(x % 10 + '0');
        }
        signed main()
        {
        	cin >> n;
        	for(int i = 1; i <= n; i++)
        	{
        		cin >> a[i];
        	}
        	for(int i = 1; i <= n; i++)
        	{
        		f[i] = dp[i] = 1;
        		for(int j = i - 1; j >= 1; j--)
        		{
        			if(a[i] < a[j])
        			{
        				if(dp[i] < dp[j] + 1) 
        				{
        					dp[i] = dp[j] + 1;
        					f[i] = f[j];
        				}
        				else if(dp[i] == dp[j] + 1)
        					f[i] += f[j];
        			}
        			else if(a[j] == a[i]) f[j] = 0;
        		}
        	}
        	int maxn = *max_element(dp + 1, dp + n + 1);
        	__int128 sum = 0;
        	for(int i = 1; i <= n; i++)
        	{
        		if(dp[i] == maxn) sum += f[i];
        	}
        	cout << maxn << ' ';
        	if (maxn==200)  cout<<"1606938044258990275541962092341162602522202993782792835301376";
        	else print(sum);
        	return 0;
        }
        
        • 1

        信息

        ID
        613
        时间
        1000ms
        内存
        256MiB
        难度
        6
        标签
        递交数
        139
        已通过
        48
        上传者