NOI2009 诗人小G

题目链接：戳我

30pts做法：
我们设\(dp[i]\)表示前i个句子最小的代价，然后再记录一个当前的最小值是从哪里转移过来的。
注意输出的行末不带空格，以及要用long double（double和long long都会炸）

#include
#include
#include
#include
#include
#include
#define MAXN 100010
#define mp make_pair
#define ll long long
#define double long double
#define INF 1e18
using namespace std;
int T,n,l,p;
char s[MAXN][60];
double sum[MAXN];
inline double calc(double x)
{
    double cur_ans=1,xx=1.0*x;
    for(int i=1;i<=p;i++) cur_ans*=xx;
    return cur_ans;
}
namespace subtask1
{
    int last[MAXN];
    double dp[MAXN];
    vector >vec;
    inline void solve()
    {
        vec.clear();
        for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
        for(int i=0;i<=n;i++) dp[i]=INF*8;
        dp[0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;jINF)
        {
            printf("Too hard to arrange\n");
            return;
        }
        printf("%.0Lf\n",dp[n]);
        int now=n;
        while(now>=1)
        {
            vec.push_back(mp(last[now],now));
            now=last[now]-1;
        }
        for(int i=vec.size()-1;i>=0;i--)
        {
            for(int j=vec[i].first;j

100分做法需要决策单调性
我们考虑记录s数组表示前缀和，\(f[i]\)表示前i个的最小代价。
\(f[i]=min{f[j]+|s[i]-s[j]-1-L|}\)
其中\(j\in [0,i-1]\)
显然对于两个点j,k，且\(j。如果j能够转移到i，k能转移到i+1，那么j一定不能转移到其它大于i的点。
那么这就存在一个决策单调的性质。
我们可以维护一下么个点的作用范围。用一个单调栈加三元组记录就可以了。

#include
#include
#include
#include
#include
#include
#include
#define MAXN 100010
#define double long double
using namespace std;
int n,L,P,T,head,tail,top;
int g[MAXN],S[MAXN];
char ch[MAXN][35];
long long s[MAXN];
double f[MAXN];
struct Node{int j,l,r;}q[MAXN];
inline double fpow(double x,int y)
{
    double cur_ans=1;
    while(y)
    {
        if(y&1) cur_ans=cur_ans*x;
        x=x*x;
        y>>=1;
    }
    return cur_ans;
}
inline double calc(int i,int j)
{
    return f[j]+fpow(fabs(1.0*s[i]-s[j]-1-L),P);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    freopen("ce.out","w",stdout);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&L,&P);
        for(int i=1;i<=n;i++) 
        {
            scanf("%s",ch[i]+1);
            s[i]=1ll*strlen(ch[i]+1);
        }
        for(int i=1;i<=n;i++) s[i]+=s[i-1]+1;
        memset(q,0,sizeof(q));
        q[head=tail=1]=(Node){0,1,n};
        for(int i=1;i<=n;i++)
        {
            while(head=calc(q[tail].l,i)) tail--;
            int l=q[tail].l,r=q[tail].r,cur_ans=q[tail].r+1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(calc(mid,i)<=calc(mid,q[tail].j)) cur_ans=mid,r=mid-1;
                else l=mid+1;
            }
            if(cur_ans!=q[tail].l) q[tail].r=cur_ans-1;
            else --tail;
            if(cur_ans<=n) q[++tail]=(Node){i,cur_ans,n};
        }
        if(f[n]>1e18) printf("Too hard to arrange\n");
        else
        {
            printf("%.0Lf\n",f[n]);
            top=0;
            for(int i=n;i;i=g[i])S[++top]=i;S[top+1]=0;
            for(int i=top;i;--i)
                for(int j=S[i+1]+1;j<=S[i];++j)
                {
                    printf("%s",ch[j]+1);
                    if(j!=S[i]) printf(" ");
                    else printf("\n");
                }
        }
        printf("--------------------\n");
    }
    return 0;
}
动态规划——决策单调性

相关

标签