常州集训9DAY

今天老师带我们又加强了动规的运用，如下：动态规划3
及代码：

#include<bits/stdc++.h>
using namespace std;

char a[50];
int tmp[1010];
int n,k,lent;
struct node{
  int s[1010],len;
}f[50][10];

void work(int x,int y,int form,int to){

  int nn[50];
  int lenn=0;
  for(int i=to;i>=form;i--)nn[++lenn]=a[i]-&#039;0&#039;;
  lent=max(f[x][y].len,lenn);
  for(int i=1;i<=f[x][y].len;i++){
    for(int j=1;j<=lenn;j++){
      tmp[i+j-1]+=f[x][y].s[i]*nn[j];
    }
  }
  for(int i=1;i<=lent;i++){
    tmp[i+1]+=tmp[i]/10;
    tmp[i]%=10;
  }
  while(tmp[lent+1]>0){
    lent++;
    tmp[lent+1]+=tmp[lent]/10;
    tmp[lent]%=10;
  }

}

bool cmp(int x,int y){
  if(lent<f[x][y].len) return false;
  if(lent>f[x][y].len) return true;
  for(int i=lent;i>=1;i--)
  {
    if(f[x][y].s[i]>tmp[i])return false;
    if(f[x][y].s[i]<tmp[i])return true;
  }
  return false;
}

int main(){
  freopen("maxmin.in","r",stdin);
  freopen("maxmin.out","w",stdout);
  cin>>n>>k;
  cin>>a+1;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=i;j++)f[i][0].s[j]=a[i-j+1]-&#039;0&#039;;
    f[i][0].len=i;
  }

  for(int j=1;j<=k;j++)
     for(int i=j+1;i<=n;i++)
     {
       for(int l=j;l<i;l++)
       {
            memset(tmp,0,sizeof(tmp));
            work(l,j-1,l+1,i);
            if(cmp(i,j))
            {
              for(int p=1;p<=lent;p++)f[i][j].s[p]=tmp[p];
              f[i][j].len=lent;
            }
      }
     }

   for(int i=f[n][k].len;i>=1;i--)
        cout<<f[n][k].s[i];
   return 0;
}

也是没听懂一点一点还是有的。然后下午打题的时候跟旁边的大神同桌学习了一下代码，据说以下代码能让cin跑得比scanf快：

ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);