为什么我的初始化memset出问题了???
去掉就AC了???
求解释
代码:
#include<bits/stdc++.h>
using namespace std;
namespace FAST_IO
{
template<typename T> void read(T &a)
{
a=0;
int f=1;
char c=getchar();
while(!isdigit(c))
{
if(c=='-')
{
f=-1;
}
c=getchar();
}
while(isdigit(c))
{
a=a*10+c-'0';
c=getchar();
}
a=a*f;
}
template <typename T> void write(T a)
{
if(a<0)
{
a=-a;
putchar('-');
}
if(a>9)
{
write(a/10);
}
putchar(a%10+'0');
}
template <typename T> void writeln(T a)
{
write(a);
puts("");
}
}
const int maxn=2e5+100;
const long double ma=1e18;
int t;
int n,l,p;
string s[maxn];
int len[maxn];
long double sum[maxn],Next[maxn];
long double dp[maxn];
int last[maxn];
struct node
{
int c,l,r;
};
node q[maxn];
int head=1,tail=1;
long double power(long double a,long long n)
{
long double result=1;
while(n)
{
if(n&1)
{
result*=a;
}
a*=a;
n>>=1;
}
return (result);
}
long double _abs(long double x)
{
if(x<0)
{
return -x;
}
return x;
}
long double val(int j,int i)//dp[j]->dp[i]
{
return dp[j]+power(_abs(sum[i]-sum[j]+i-j-1-l),p);
}
void output()
{
if(dp[n]>ma)
{
puts("Too hard to arrange");
}
else
{
printf("%.0Lf\n",dp[n]);
for(int i=n; i; i=last[i])
{
Next[last[i]]=i;
}
int now=0;
for(int i=1; i<=n; ++i)
{
now=Next[now];
for(int j=i; j<now; ++j)
{
cout<<s[j]<<" ";
}
cout<<s[now]<<endl;
i=now;
}
}
puts("--------------------");
}
int main()
{
// freopen("P1912_2.in","r",stdin);
// freopen("P1912_2.ans","w",stdout);
cin>>t;
while(t--)
{
// memset(last,0,sizeof(last));
// memset(sum,0,sizeof(sum));
// memset(q,0,sizeof(q));
// memset(dp,0,sizeof(dp));
cin>>n>>l>>p;
for(int i=1; i<=n; i++)
{
cin>>s[i];
len[i]=s[i].size();
sum[i]=sum[i-1]+len[i];
}
head=tail=1;
q[1]=(node)
{
0,1,n
};
// memset(dp,0x3f,sizeof(dp));
// dp[0]=0;
for(int i=1; i<=n; i++)
{
int pos=n+1;
while(head<tail&&q[head].r<i)
{
head++;
}
q[head].l=i;
dp[i]=val(q[head].c,i);
last[i]=q[head].c;
while(head<tail&&val(i,q[tail].l)<=val(q[tail].c,q[tail].l))
{
pos=q[tail].l;
tail--;
}
if(head<tail&&val(i,q[tail].r)>=val(q[tail].c,q[tail].r))//c means choose
{
goto A;
}
else
{
//只要在tail上二分
int now=q[tail].c;
int ls=q[tail].l,rs=q[tail].r;
while(ls<=rs)
{
int mid=ls+rs>>1;
if(val(i,mid)<=val(now,mid))
{
rs=mid-1;
pos=mid;
}
else
{
ls=mid+1;
}
}
q[tail].r=pos-1;
}
A:
if(pos!=n+1)
{
tail++;
q[tail]=(node){i,pos,n};
}
// for(int j=0;j<i;j++)
// {
// dp[i]=min(dp[i],dp[j]+(long long)pow(abs(sumlen[i]-sumlen[j]+i-j-1-l),p));
// }
}
output();
}
}