题解 P4713 【「语文」凑字数】

· · 题解

Emmmm和出题人交流了一下，发现自己的算法没问题

也成功拿到最快的44ms

我来说一下我的做法吧，这个做法的复杂度非常的优越

首先我们肯定是要 2^k去枚举每个部分的状态的

复杂度优化的关键在于Dp

我们发现如果固定扣的分数，那么行数自然是尽量大。在行数一样大的情况下自然是最后一行字越多越好。

我们发现可以在dp的基础上贪心。

我们设f[i][j]为 dp到第i个句子，现在扣了j分

f[i][j]是一个pair，保存着两个值 行数 最后一行的字数

这样Dp的复杂度是 n·cnt·S cnt是不会扣到0的部分的数量

2^k种状态的cnt加和是 k*2^(k-1)

所以最后的复杂度是 2^(k-1)kSn == 80 · 200 · 200

非常优越的复杂度，甚至可以把S，n提高到300都可以做

附上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
pair<int,int> f[201][1005];
int n,m,L,K,S,C;
int A[205];
int s[205][11];
bool vis[201][1005],ok[11];
void up(int i,int j,int a,int b){
    if(!vis[i][j]){
        vis[i][j]=1;
        f[i][j]=make_pair(a,b);
    }
    else{
        if(f[i][j].first>a)return;
        if(f[i][j].first<a)
            f[i][j]=make_pair(a,b);
        else
            f[i][j].second=max(f[i][j].second,b);
    }
}
int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&L,&K,&S,&C);
    for(int i=1;i<=n;i++) scanf("%d",&A[i]);
    for(int i=1;i<n;i++)
        for(int j=0;j<K;j++) 
            scanf("%d",&s[i][j]);
    int ans=0;
    for(int t=1;t<(1<<K);t++){
        memset(vis,0,sizeof(vis));
        for(int i=0;i<K;i++) ok[i]=(t>>i)&1;
        int cnt=0,a,b,c,d,e;
        for(int i=0;i<K;i++) cnt+=ok[i];
        a=(A[1]+2)/L;b=(A[1]+2)%L;
        if(!b) b=L;
        else a++;
        f[1][0]=make_pair(a,b);vis[1][0]=1;
        for(int i=1;i<n;i++)
            for(int j=0;j<=cnt*S;j++)
                if(vis[i][j]){
                    a=f[i][j].first,b=f[i][j].second;
                    e=0;
                    c=a-1+(b+A[i+1])/L,d=(b+A[i+1])%L;
                    if(!d) d=L; else c++;
                    for(int k=0;k<K;k++) if(ok[k]&&s[i][k]<0) e-=s[i][k];
                    if(j+e<=cnt*S) up(i+1,j+e,c,d);
                    e=0;
                    c=a+(A[i+1]+2)/L,d=(A[i+1]+2)%L;
                    if(!d) d=L; else c++;
                    for(int k=0;k<K;k++) if(ok[k]&&s[i][k]>0) e+=s[i][k];
                    if(j+e<=cnt*S) up(i+1,j+e,c,d);
                }
        int total=cnt*S,zm;
        for(int j=0;j<=cnt*S;j++) if(vis[n][j]){
            zm=total-j;
            if(f[n][j].first<m) zm-=(m-f[n][j].first)*C;
            ans=max(ans,zm);
        } 
    }
    cout<<ans<<endl;
}