about 4 years ago
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 5001
#define Mod 100000000
using namespace std;
int dp[2][maxn]={0},sum[2][maxn]={0};
char a[maxn],b[maxn];
int n,m;
void add(int &x,int y)
{
x=(x+y)%Mod;
}
void dec(int &x,int y)
{
x=(x-y+Mod)%Mod;
}
int main()
{
scanf("%s%s",a+1,b+1);
int i,j,now;
n=strlen(a+1)-1;m=strlen(b+1)-1;
for (i=0;i<=m;i++) sum[0][i]=1;
for (i=1;i<=n;i++)
{now=i&1;
memset(dp[now],0,sizeof(dp[now]));
memset(sum[now],0,sizeof(sum[now]));
sum[now][0]=1;
for (j=1;j<=m;j++)
{ //一开始自己yy的。注意最后一步减去是重点。
if (a[i]==b[j]) dp[now][j]=dp[now^1][j-1]+1;
dp[now][j]=max(dp[now^1][j],max(dp[now][j-1],dp[now][j]));
if (a[i]==b[j]&&dp[now][j]==dp[now^1][j-1]+1) add(sum[now][j],sum[now^1][j-1]);
if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);
if (dp[now][j]==dp[now][j-1]&&dp[now^1][j-1]==dp[now^1][j]&&dp[now^1][j]==dp[now][j-1])dec(sum[now][j],sum[now^1][j-1]);
//如果a[i]!=b[j]，dp[now][j-1]==dp[now^1][j],则说明他们==dp[now^1][j-1]
// 这样的话就会多算一遍，必须减去【MARK!!】
/* WYL版。简单直白。
if (a[i]==b[j])
{dp[now][j]=dp[now^1][j-1]+1;
dp[now][j]=max(dp[now^1][j],max(dp[now][j-1],dp[now][j]));
if (dp[now][j]==dp[now^1][j-1]+1) add(sum[now][j],sum[now^1][j-1]);
if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);}
else
{
dp[now][j]=max(dp[now^1][j],dp[now][j-1]);
if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);
if (dp[now^1][j]==dp[now][j-1]&&dp[now^1][j-1]==dp[now][j-1])
//if (dp[now][j]==dp[now^1][j-1])也是满足的，因为不可能dp[now][j-1],dp[now^1][j]<dp[now^1][j-1]
dec(sum[now][j],sum[now^1][j-1]);
}*/
}}
printf("%d\n%d\n",dp[n&1][m],sum[n&1][m]);
}
about 4 years ago
学了好久调了好久……
仙人掌dp分成在环上和树上就好
但是有很多的细节要注意
论静态查错是多么的重要
代码还有一点小问题，sth大爷的数据没有全过。poj的还没试过
-------------------------update--------------------------------
fe是为了判断二元环而设的，但是此题二元环可直接当树边处理，没有影响。用fa判断即可
而且用fe会在sth的数据上wa3个点
但是sth用feA了自己的数据……
但是他的边从1开始……0.0不知道怎么异或找的相反边……
仙人掌最多有多少条边的计算一开始也不知道……poj mle。。
初步计算应该是最坏情况下是二元环，这样就是n*2条边，加上反向边4*n
代码中用fe的地方注释掉了换成了fa
于是冲到了pojrank1……
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define maxn 50001
#define maxm 200001
using namespace std;
int next[maxm],point[maxn],v[maxm];
int dfn[maxn],low[maxn],fe[maxn],f[maxn],fa[maxn];
int n,m,widen=-1,ans=0,tot=0;
int loop[maxn*2],ln=0,start,til;
struct node
{int num,pos;} q[maxn*2];
inline int readln()
{
char c=getchar();int result=0,bj=1;
while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
if (c=='-') bj=-1,c=getchar();
while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
return result*bj;
}
inline void addedge(int x,int y)
{
widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;
widen++;next[widen]=point[y];point[y]=widen;v[widen]=x;
}
void workonloop()
{
int i,x;
memcpy(loop+ln+1,loop+1,sizeof(int)*ln);
q[1].pos=1;q[1].num=f[loop[1]]-1;
start=1;til=1;
for (i=2;i<=ln*2;i++)//注意下面所有都是环上的！！！
{
for (;q[start].pos<i-(ln)/2;start++);
ans=max(ans,q[start].num+f[loop[i]]+i);
x=f[loop[i]]-i;
for (;start<=til&&q[til].num<=x;til--);//会出现start>til的情况！！
q[++til].num=x;q[til].pos=i;
}
}
void dfs(int x)
{
dfn[x]=low[x]=++tot;
for (int k=point[x];k!=-1;k=next[k])
if (fa[x]!=v[k])
// if ((k^1)!=fe[x])
{
if (dfn[v[k]])
low[x]=min(low[x],dfn[v[k]]);
else
{
fe[v[k]]=k;fa[v[k]]=x;dfs(v[k]);
low[x]=min(low[x],low[v[k]]);
}
}
for (int k=point[x];k!=-1;k=next[k])
if (fa[x]!=v[k])
// if ((k^1)!=fe[x])
{
if (low[v[k]]>dfn[x])//在以x为根的子树里
{
ans=max(ans,f[x]+1+f[v[k]]);
f[x]=max(f[x],f[v[k]]+1);
}
else
if (fa[v[k]]!=x&&dfn[x]<dfn[v[k]])
//if (fe[v[k]]!=k&&dfn[x]<dfn[v[k]])//非树边且x点是靠上的点
{
ln=0;int now=v[k];
for (;x!=now;now=fa[now])
loop[++ln]=now;
loop[++ln]=x;
workonloop();
for (int i=1;i<ln;i++)
f[x]=max(f[x],f[loop[i]]+min(i,ln-i));
}
}
}
int main()
{
int i,j,k,x,y;
memset(point,-1,sizeof(point));
memset(next,-1,sizeof(next));
n=readln();m=readln();
for (i=1;i<=m;i++)
{
k=readln();x=readln();
for (j=1;j<k;j++,x=y)
{
y=readln();
addedge(x,y);
}
}
dfs(1);
printf("%d\n",ans);
}
almost 4 years ago
题目很恶心……
注意僵尸是可以复活的。新加的僵尸排在最前面
但是做的时候依旧是从后面添僵尸
【具体看gty的题解……】
很明显可以维护一个凸壳。点坐标为（i*d,sum[i]）
查询的时候只需要找（xi+i*d,sum[i]）与点j斜率最大的即可
下凸壳
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define kk I64d
#define maxn 100001
#define eps 1e-6
using namespace std;
long double result=0.0;
int stack[maxn];
long long d;int n,top=0;
long long a[maxn]={0},sum[maxn]={0},x[maxn]={0};
long long readln()
{
char c=getchar();long long result=0;int bj=1;
while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
if (c=='-') bj=-1,c=getchar();
while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
return result*bj;
}
double fabs(double a)
{
if (a>0) return a; else return -a;
}
int dcmp(double a,double b)
{
if (fabs(a-b)<eps) return 0;
if (a>b) return 1;else return -1;
}
double xl(int a,int b)
{
return (sum[a]-sum[b-1])/(x[a]+d*a-d*b);
}
double xltb(int a,int b)
{
return (sum[a-1]-sum[b-1])/(d*a-d*b);
}
int find(int left,int right,int k)
{
int lmid,rmid;
while (left+1<right)
{
lmid=left+(right-left+1)/3;rmid=left+(right-left+1)*2/3;
if (dcmp(xl(k,lmid),xl(k,rmid))>0) right=rmid-1;
else left=lmid+1;
}
if (dcmp(xl(k,left),xl(k,right))>0) return left;
else return right;
}
int main()
{
int i,k;
n=readln();d=readln();
for (i=1;i<=n;i++)
{
a[i]=readln();x[i]=readln();sum[i]=sum[i-1]+a[i];
}
for (i=1;i<=n;i++)
{
while (top>=2&&dcmp(xl(i,stack[top-1]),xl(i,stack[top]))<0) top--;
stack[++top]=i;
k=find(1,top,i);
result+=(sum[i]-sum[k-1])/(long double)(x[i]+d*i-d*k);
}
printf("%d\n",(int)(result+0.5));
}
almost 4 years ago
ac自动机多和dp联系在一起
http://hi.baidu.com/wwwaaannngggrs/item/b2b67acccea55f0dc710b211
f数组是邻接矩阵，自乘k次代表沿矩阵走k步，f[i][j]表示i到j的方案数
f[i][j] 是j转移到i的可能性
ans数组是结果。由于在数组里的下标都往后移了一位,ans[1][1]=f[0][0]=1【1、第0位匹配根节点的概率是100%。2、若为0的话会导致答案乘0失解】
f*ans的答案ans'[i][j] 代表n个点下一步转移到i点的可能性【注意矩阵乘法不满足交换律！！！！注意查错！被坑了好久……】
代码里有重载。
orz gty
/**************************************************************
Problem: 2553
User: LaVenDer
Language: C++
Result: Accepted
Time:60 ms
Memory:1376 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
struct matrix
{
long double a[80][80];
int sx,sy;
void dowith(int x,int y)
{
sx=x;sy=y;memset(a,0,sizeof(a));
}
} ans,f;
matrix operator*(const matrix a,const matrix b)
{
matrix temp;temp.dowith(a.sx,b.sy);
for (int i=1;i<=temp.sx;i++)
for (int j=1;j<=temp.sy;j++)
{
for (int k=1;k<=a.sy;k++)
temp.a[i][j]+=a.a[i][k]*b.a[k][j];
}
return temp;
}
struct ac
{
int ch[101][27];
int fail[101],last[101],val[101];
int sz,size;
void dowith(int k)
{
sz=0;size=k;
memset(fail,0,sizeof(fail));
memset(last,0,sizeof(last));
memset(val,0,sizeof(val));
memset(ch,0,sizeof(ch));
}
void insert(char *st,int color)
{
int l=strlen(st),i;
int pos=0;
for (i=0;i<l;i++)
st[i]=st[i]-'a'+1;
for (i=0;i<l;i++)
{
if (!ch[pos][st[i]]) {ch[pos][st[i]]=++sz;}
pos=ch[pos][st[i]];
}
val[pos]=color;
}
queue<int>q;
void prepare()
{
int i,j,a,k,pos=0;
for (i=1;i<=size;i++)
if (ch[pos][i]) q.push(ch[pos][i]);
while (!q.empty())
{
pos=q.front();q.pop();
for (i=1;i<=size;i++)
{
if (!ch[pos][i]){ch[pos][i]=ch[fail[pos]][i];continue;}
q.push(ch[pos][i]);
j=fail[pos];
while (j&&!ch[j][i]) j=fail[j];
j=ch[j][i];
fail[ch[pos][i]]=j;
}
}
}
} t;
int n,len,alphabet;
char st[20];
matrix ksm(matrix f,int x)
{
matrix temp;temp.dowith(f.sx,f.sy);
for (int i=1;i<=f.sx;i++)
temp.a[i][i]=1;
for (int i=x;i>0;i>>=1)
{
if (i&1) temp=temp*f;
f=f*f;
}
return temp;
}
int main()
{
int i,j,k;
scanf("%d%d%d",&n,&len,&alphabet);
t.dowith(alphabet);
for (i=1;i<=n;i++)
{
scanf("%s",st);
t.insert(st,i);
}
t.prepare();
f.dowith(t.sz+2,t.sz+2);
long double temp=1.0/(long double)alphabet;
for (i=0;i<=t.sz;i++)
{
for (j=1;j<=alphabet;j++)
if (t.val[i]==0)
{
if (t.val[t.ch[i][j]])
{
f.a[1][i+1]+=temp;
f.a[t.sz+2][i+1]+=temp;
}
else
f.a[t.ch[i][j]+1][i+1]+=temp;
}
}
f.a[t.sz+2][t.sz+2]=1;
f=ksm(f,len);
ans.dowith(t.sz+2,1);
ans.a[1][1]=1;
ans=f*ans;
printf("%.12lf\n",(double)ans.a[t.sz+2][1]);
}
almost 4 years ago
终于对斜率优化有了一点理解……
calc(x,y)<g[t] 则x比y要优。calc（x，y）的值其实就是斜率
在入队的时候，设i<j<k,若calc(k,j)<calc（j,i）【斜率的比较。即维护凸壳】则无论calc是否大于g[t],j都不会是最优决策 弹出
出队时只需要找到calc(x,y)<g[t]中最优的x即可
坑啊……注意int*int=long long 的话会爆==开心的栽在了这里半个小时……
/**************************************************************
Problem: 1010
User: Lavender6895
Language: C++
Result: Accepted
Time:136 ms
Memory:2368 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 50001
using namespace std;
int q[maxn+5]={0},c[maxn]={0};
long long f[maxn]={0},g[maxn]={0},sum[maxn]={0};
int n,l;
double calc(int x,int y)
{
return ((double)f[x]-f[y]+g[x]*g[x]-g[y]*g[y])/(2*g[x]-2*g[y]);
}
int readln()
{
char c;int result=0,bj=1;
while (c!='-'&&(!(c<='9'&&c>='0'))) c=getchar();
if (c=='-') {bj=-1;c=getchar();}
while (c<='9'&&c>='0') {result=result*10+c-'0';c=getchar();}
return result*bj;
}
int main()
{
n=readln();l=readln();
long long s=0;int i,start,til,k;
for (i=1;i<=n;i++) c[i]=readln(),s+=c[i],g[i]=s+i;
start=1;til=1;q[start]=0;
for (i=2;i<=n;i++)
{
while (start<til&&calc(q[start+1],q[start])<g[i]-l-1) start++;
k=q[start];
f[i]=f[k]+(g[i]-g[k]-(l+1))*(g[i]-g[k]-(l+1));
while (start<til&&calc(i,q[til])<calc(q[til],q[til-1])) til--;
q[++til]=i;
}
printf("%lld\n",f[n]);
}
almost 4 years ago
终于发现了自己的手残
因为范围不大所以用搜索来转移状态。
转移的时候用了射线法
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
struct node{int x,y,num;};
queue<node> q;
int f[12][12][1<<11],n,m,d,ans=0,a[12],v[1<<11],pos[12][2];
char map[12][12];
const int dx[4]={-1,0,0,1};
const int dy[4]={0,-1,1,0};
int calc(int num,int x,int y,int xx)
{
for (int i=1;i<=d;i++)
if (pos[i][1]>y&&(x==pos[i][0]&&xx>pos[i][0]||xx==pos[i][0]&&x>pos[i][0])) num=num^(1<<i-1);
return num;
}
int get(int st,int x,int y,int xx)
{
for(int i=1;i<=d;i++)
if(y<pos[i][1]&&(x==pos[i][0]&&xx>pos[i][0]||x>pos[i][0]&&xx==pos[i][0]))
st^=1<<i-1;
return st;
}
void search(int x,int y)
{
int i,xx,yy,num;
memset(f,-1,sizeof(f));
q.push((node){x,y,0} );f[x][y][0]=0;
while (!q.empty())
{
node temp=q.front();q.pop();
for (i=0;i<4;i++)
{
xx=temp.x+dx[i];yy=temp.y+dy[i];
if (xx<=n&&xx>=1&&yy<=m&&yy>=1&&map[xx][yy]=='0')
{
num=get(temp.num,temp.x,temp.y,xx);
if (f[xx][yy][num]==-1)
{
f[xx][yy][num]=f[temp.x][temp.y][temp.num]+1;
q.push((node){xx,yy,num});
}
}
}
}
for (i=1;i<(1<<d);i++) if (f[x][y][i]!=-1) ans=max(ans,v[i]-f[x][y][i]);
}
int main()
{
int i,j,posn=0,k;
scanf("%d%d%d",&n,&m,&d);
for (i=1;i<=d;i++) scanf("%d",&a[i]);
for (i=1;i<(1<<d);i++) for (j=i,k=1;k<=d;k++) if (j&(1<<k-1)) v[i]+=a[k];
for (i=1;i<=n;i++)
{
scanf("%s",map[i]+1);
for (j=1;j<=m;j++)
if (map[i][j]!='0'&&map[i][j]!='#') pos[map[i][j]-'0'][0]=i,pos[map[i][j]-'0'][1]=j;
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) if(map[i][j]=='0') search(i,j);
printf("%d\n",ans);
}
