搜狐后两道编程题感觉应该用动态规划，不知怎么下手

过河是贪心吧

项链那题思路是什么？

项链 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; char a[5000010]; int sum[2000010][5]; int n; bool check(int x) { int i,j,k; int m=n-x; for(i=1;i<=n;i++) { for(j=0;j<5;j++) if(sum[i+m-1][j]-sum[i-1][j]<1) break; if(j==5) return true; } return false; } int main() { int i,j,k; while(scanf("%s",a+1)!=EOF) { memset(sum,0,sizeof(sum)); n=strlen(a+1); for(i=n+1;i<=2*n;i++) a[i]=a[i-n]; //cout<<a+1<<endl; for(i=1;i<=2*n;i++) { int s=a[i]-'A'; //cout<<s<<endl; for(j=0;j<5;j++) { if(s==j) sum[i][j]=sum[i-1][j]+1; else sum[i][j]=sum[i-1][j]; } } int l=1; int r=n; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid-1; } cout<<r<<endl; } return 0; } 删除数位 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; char a[5000010]; int sum[2000010][5]; int n; bool check(int x) {     int i,j,k;     int m=n-x;     for(i=1;i<=n;i++)     {         for(j=0;j<5;j++)             if(sum[i+m-1][j]-sum[i-1][j]<1)                 break;         if(j==5)             return true;     }     return false; } int main() {     int i,j,k;     while(scanf("%s",a+1)!=EOF)     {         memset(sum,0,sizeof(sum));         n=strlen(a+1);         for(i=n+1;i<=2*n;i++)             a[i]=a[i-n];         //cout<<a+1<<endl;         for(i=1;i<=2*n;i++)         {             int s=a[i]-'A';             //cout<<s<<endl;             for(j=0;j<5;j++)             {                 if(s==j)                     sum[i][j]=sum[i-1][j]+1;                 else                     sum[i][j]=sum[i-1][j];             }         }         int l=1;         int r=n;         while(l<=r)         {             int mid=(l+r)>>1;             if(check(mid))                 l=mid+1;             else                 r=mid-1;         }         cout<<r<<endl;     }     return 0; } 过河 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; char a[5000010]; int sum[2000010][5]; int n; bool check(int x) {     int i,j,k;     int m=n-x;     for(i=1;i<=n;i++)     {         for(j=0;j<5;j++)             if(sum[i+m-1][j]-sum[i-1][j]<1)                 break;         if(j==5)             return true;     }     return false; } int main() {     int i,j,k;     while(scanf("%s",a+1)!=EOF)     {         memset(sum,0,sizeof(sum));         n=strlen(a+1);         for(i=n+1;i<=2*n;i++)             a[i]=a[i-n];         //cout<<a+1<<endl;         for(i=1;i<=2*n;i++)         {             int s=a[i]-'A';             //cout<<s<<endl;             for(j=0;j<5;j++)             {                 if(s==j)                     sum[i][j]=sum[i-1][j]+1;                 else                     sum[i][j]=sum[i-1][j];             }         }         int l=1;         int r=n;         while(l<=r)         {             int mid=(l+r)>>1;             if(check(mid))                 l=mid+1;             else                 r=mid-1;         }         cout<<r<<endl;     }     return 0; }