2 条题解

  • 0
    @ 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;
    }
    
    • 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

      信息

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