2 条题解

  • 0
    @ 2025-10-8 16:55:05
    #include <bits/stdc++.h>
    using namespace std;
    char dc[205][15];int b[205];
    bool f[200005];
    char s[200005];
    int main()
    {
        int n=1;
        while(scanf("%s",dc[n]))
        {
            if(dc[n][0]=='.')break;
    		b[n]=strlen(dc[n]);
            n++;
        }
        n--;
        int len=0;
        while(scanf("%s",s+len+1)!=EOF)
    	{
    		len=strlen(s+1);
    	}
        
    	memset(f,0,sizeof(f));f[0]=True;
        for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=n;j++)
            	if(i>=b[j])
                {
                    if(strncmp(s + i - b[j] + 1, dc[j], b[j]) == 0)
                        f[i] |= f[i - b[j]];
                }
        }
        int p=len;while(!f[p])p--;
        printf("%d\n",p);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:54:55
      #include<bits/stdc++.h>
      using namespace std;
      char dc[205][15];int b[205];
      bool f[200005];
      char s[200005];
      int main()
      {
          int n=1;
          while(scanf("%s",dc[n]))
          {
              if(dc[n][0]=='.')break;
      		b[n]=strlen(dc[n]);
              n++;
          }
          n--;
          int len=0;
          while(scanf("%s",s+len+1)!=EOF)
      	{
      		len=strlen(s+1);
      	}
          
      	memset(f,0,sizeof(f));f[0]=True;
          for(int i=1;i<=len;i++)
          {
              for(int j=1;j<=n;j++)
              	if(i>=b[j])
                  {
                      if(strncmp(s + i - b[j] + 1, dc[j], b[j]) == 0)
                          f[i] |= f[i - b[j]];
                  }
          }
          int p=len;while(!f[p])p--;
          printf("%d\n",p);
          return 0;
      }
      • 1

      *【背包:匹配型背包】[IOI 1996 / USACO2.3] 最长前缀 Longest Prefix

      信息

      ID
      1011
      时间
      1000ms
      内存
      128MiB
      难度
      4
      标签
      递交数
      38
      已通过
      18
      上传者