牛客练习赛36-白红宇

牛客练习赛36

阅读量：5344 次

发布时间：2019-06-15

本文共 2011 字，大约阅读时间需要 6 分钟。

就是最小表示法啊

#include
    
     #include
     
      #include
      
       #define M 2010000using namespace std;int k,m,n,b,l,r;char c[M],d[M];int Min(char *s, int n){    int i=0,j=1,k;    while(i
       
        
         s[j+k])i+=k+1;        else j+=k+1;        if(i==j)j++;    }    return min(i,j);}int main(){    scanf("%d",&n);    for(int i=0;i
         
          >c[i]; if(Min(c,n)!=0) printf("YES"); else printf("NO");}

\(f[i][j]\)表示前\(i\)天工作\(j\)天最小体力消耗

每次从后往前枚举最后一段工作时间

没了

#include
    
     #include
     
      #include
      
       using namespace std;int n,m,k,f[401][401],a[401],d[410],ans;int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++) d[i]=d[i-1]+i;    memset(f,0x3f,sizeof(f)); f[0][0]=0;    for(int i=1;i<=n;i++) scanf("%1ld",&a[i]),f[i][0]=0;    for(int i=1;a[i];i++) f[i][i]=d[i];    for(int i=1;i<=n;i++)    {        if(a[i]) for(int l=1;l<=i;l++)         {            for(int j=i;j>=2 && a[j]&& i-j+1<=l;j--)             if(f[j-2][l-i+j-1]+d[i-j+1]<=k) f[i][l]=min(f[i][l],f[j-2][l-i+j-1]+d[i-j+1]);            if(f[i][l]<=k) ans=max(ans,l);        }        for(int j=1;j<=i;j++) f[i][j]=min(f[i][j],f[i-1][j]);    }    printf("%d",ans);}

ZUTTER用优秀的\(O(n^3)\)加边界优化把它卡过去了！！！！

这个故事告生动诉我们一个真理人有多大胆，地有多大产

正解

为了去掉所有任务的限制先给每个工作分一天，把\(V[2]-V[n]\)整体建\(V[1]\)

然后这不就是一个完全背包了嘛！！！

\(O(n^2)\)解决

ZUTTER的心理动向

感觉只有\(O(n^3)\)做法啊

怕不是斜率优化\单调性优化\线段树优化

可是我不会啊！！！

2≤ N,K≤ 2000,K≤ W≤ min(4000,2*K)

矮这个\(w\)范围比\(n,k\)只大一倍有点奇怪啊

把\(n\)提到最外层再枚举\(w\)再枚举\(k\)感觉会快很多啊

经过一波冷静分析似乎复杂度挺有前途的!!??

#include
      
       #include
       
        #include
        
         using namespace std;int i,m,n,j,k,a[2001],w,f[4001][2001];int main(){  scanf("%d%d%d",&n,&k,&w);  for(int i=1;i<=n;i++) scanf("%d",&a[i]);  memset(f,-0x3f,sizeof(f));  f[0][0]=0;  for(int i=1;i<=n;i++)       for(int j=0;j<=w-i;j++)          for(int l=max(0,k-(w-j)/i);l