开学那个月学了点新东西，不知道还记不记得了，mark一下
感觉cdq的论文讲的很详细
题主要跟着kuangbin巨做了几道基础的
http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710343.html
还有几道没做，留着坑
感觉广义括号表示法虽然神奇，但一般最小表示法就够用了吧，感觉最小表示法更直观一点
hdu1693
1 #include2 #include 3 #include 4 typedef long long ll; 5 using namespace std; 6 ll f[13][13][1<<13]; 7 int a[13][13]; 8 int n,m,cas; 9 10 int main()11 {12 scanf("%d",&cas);13 for (int tt=1; tt<=cas; tt++)14 {15 scanf("%d%d",&n,&m);16 for (int i=1; i<=n; i++)17 for (int j=1; j<=m; j++)18 scanf("%d",&a[i][j]);19 printf("Case %d: ",tt);20 memset(f,0,sizeof(f));21 f[0][m][0]=1;22 for (int i=1; i<=n; i++)23 {24 for (int j=0; j<(1<
poj1793（男人八题!）
1 #include2 #include 3 #include 4 typedef long long ll; 5 const int mo=30007; 6 const int maxl=1000010; 7 using namespace std; 8 struct node{ 9 int p[mo],nex[maxl],len; 10 ll st[maxl],f[maxl]; 11 void clr() 12 { 13 len=0; memset(p,255,sizeof(p)); 14 } 15 void push(ll nw,ll s) 16 { 17 int x=nw%mo; 18 for (int i=p[x];i!=-1; i=nex[i]) 19 if (st[i]==nw) 20 { 21 f[i]+=s; 22 return; 23 } 24 st[++len]=nw; f[len]=s; 25 nex[len]=p[x]; p[x]=len; 26 } 27 } h[2]; 28 int n,m,cas,p,ex,ey; 29 int a[15][15],b[15],v[15]; 30 31 void get(ll st) 32 { 33 for (int i=m; i>=0; i--) 34 { 35 b[i]=st&7; 36 st>>=3; 37 } 38 } 39 40 ll put() 41 { 42 memset(v,255,sizeof(v)); v[0]=0; 43 ll st=0; int t=0; 44 for (int i=0; i<=m; i++) 45 { 46 if (v[b[i]]==-1) v[b[i]]=++t; 47 b[i]=v[b[i]]; 48 st<<=3; st|=b[i]; 49 } 50 return st; 51 } 52 53 void shift() 54 { 55 for (int i=m;i; i--) b[i]=b[i-1]; 56 b[0]=0; 57 } 58 59 void work(int j,int k) 60 { 61 if (j==m) shift(); 62 h[p].push(put(),h[1-p].f[k]); 63 } 64 65 void dp(int i,int j) 66 { 67 for (int k=1; k<=h[1-p].len; k++) 68 { 69 get(h[1-p].st[k]); 70 if (!a[i][j]) 71 { 72 b[j]=b[j-1]=0; work(j,k); 73 continue; 74 } 75 int x=b[j],y=b[j-1]; 76 if (x&&y) 77 { 78 if ((x==y&&i==ex&&j==ey)||(x!=y)) 79 { 80 b[j]=b[j-1]=0; 81 if (x!=y) 82 for (int r=0; r<=m; r++) if (b[r]==x) b[r]=y; 83 work(j,k); 84 } 85 } 86 else if ((x&&!y)||(!x&&y)) 87 { 88 int r=x+y; 89 if (a[i][j+1]) {b[j]=r; b[j-1]=0; work(j,k);} 90 if (a[i+1][j]) {b[j-1]=r; b[j]=0; work(j,k);} 91 } 92 else if (a[i][j+1]&&a[i+1][j]) 93 { 94 b[j]=b[j-1]=m+1; 95 work(j,k); 96 } 97 } 98 } 99 100 int main()101 {102 char s[12];103 scanf("%d%d",&n,&m);104 while (n&&m)105 {106 memset(a,0,sizeof(a));107 for (int i=1; i<=n; i++)108 {109 scanf("%s",s+1);110 for (int j=1; j<=m; j++)111 if (s[j]=='.') a[i][j]=1;112 }113 for (int i=1; i<=m; i++)114 {115 a[n+2][i]=1;116 a[n+1][i]=(i>1&&i
fzu1977
1 #include2 #include 3 #include 4 typedef long long ll; 5 const int mo=30007; 6 const int maxl=300010; 7 using namespace std; 8 struct node{ 9 int p[mo],nex[maxl],len; 10 ll st[maxl],f[maxl]; 11 void clr() 12 { 13 len=0; memset(p,255,sizeof(p)); 14 } 15 void push(ll nw,ll s) 16 { 17 int x=nw%mo; 18 for (int i=p[x];i!=-1; i=nex[i]) 19 if (st[i]==nw) 20 { 21 f[i]+=s; 22 return; 23 } 24 st[++len]=nw; f[len]=s; 25 nex[len]=p[x]; p[x]=len; 26 } 27 } h[2]; 28 int n,m,cas,p,ex,ey; 29 int a[15][15],b[15],v[15]; 30 31 void get(ll st) 32 { 33 b[m+1]=st&1; st>>=1; 34 for (int i=m; i>=0; i--) 35 { 36 b[i]=st&7; 37 st>>=3; 38 } 39 } 40 41 ll put() 42 { 43 memset(v,255,sizeof(v)); v[0]=0; 44 ll st=0; int t=0; 45 for (int i=0; i<=m; i++) 46 { 47 if (v[b[i]]==-1) v[b[i]]=++t; 48 b[i]=v[b[i]]; 49 st<<=3; st|=b[i]; 50 } 51 st<<=1; st|=b[m+1]; 52 return st; 53 } 54 55 void shift() 56 { 57 for (int i=m;i; i--) b[i]=b[i-1]; 58 b[0]=0; 59 } 60 61 void dp(int i,int j) 62 { 63 for (int k=1; k<=h[p^1].len; k++) 64 { 65 get(h[p^1].st[k]); 66 if (!a[i][j]) 67 { 68 b[j]=b[j-1]=0; 69 h[p].push(put(),h[p^1].f[k]); 70 continue; 71 } 72 int x=b[j],y=b[j-1]; 73 if (b[m+1]) 74 { 75 if (!x&&!y&&a[i][j]!=1) 76 { 77 b[j]=b[j-1]=0; 78 h[p].push(put(),h[p^1].f[k]); 79 } 80 continue; 81 } 82 if (x&&y) 83 { 84 b[j]=b[j-1]=0; 85 if (x!=y){ 86 for (int r=0; r<=m; r++) if (b[r]==x) b[r]=y; 87 } 88 else b[m+1]=1; 89 h[p].push(put(),h[p^1].f[k]); 90 } 91 else if ((x&&!y)||(!x&&y)) 92 { 93 int r=x+y; 94 if (a[i][j+1]) 95 { 96 b[j]=r; b[j-1]=0; 97 h[p].push(put(),h[p^1].f[k]); 98 } 99 if (a[i+1][j])100 {101 b[j-1]=r; b[j]=0;102 h[p].push(put(),h[p^1].f[k]);103 }104 }105 else {106 if (a[i][j+1]&&a[i+1][j])107 {108 b[j]=b[j-1]=m+1;109 h[p].push(put(),h[p^1].f[k]);110 }111 if (a[i][j]==2)112 {113 b[j]=b[j-1]=0;114 h[p].push(put(),h[p^1].f[k]);115 }116 }117 }118 }119 120 int main()121 {122 char s[15]; int cas;123 scanf("%d",&cas);124 for (int tt=1; tt<=cas; tt++)125 {126 scanf("%d%d",&n,&m);127 memset(a,0,sizeof(a));128 for (int i=1; i<=n; i++)129 {130 scanf("%s",s+1);131 for (int j=1; j<=m; j++)132 if (s[j]=='O') a[i][j]=1;133 else if (s[j]=='*') a[i][j]=2;134 }135 h[0].clr();136 h[0].push(0,1); p=0;137 for (int i=1; i<=n; i++)138 {139 p^=1; h[p].clr();140 for (int k=1; k<=h[p^1].len; k++)141 {142 get(h[p^1].st[k]); shift();143 h[p].push(put(),h[p^1].f[k]);144 }145 for (int j=1; j<=m; j++)146 {147 p^=1; h[p].clr();148 dp(i,j);149 }150 }151 ll ans=0;152 for (int i=1; i<=h[p].len; i++)153 ans+=h[p].f[i];154 printf("Case %d: %I64d\n",tt,ans);155 }156 return 0;157 }
hdu3377
1 #include2 #include 3 #include 4 typedef long long ll; 5 const int mo=30007; 6 const int maxl=1000010; 7 const int inf=-100000007; 8 using namespace std; 9 struct node{ 10 int p[mo],nex[maxl],len,f[maxl]; 11 ll st[maxl]; 12 void clr() 13 { 14 len=0; memset(p,255,sizeof(p)); 15 } 16 void push(ll nw,int s) 17 { 18 int x=nw%mo; 19 for (int i=p[x];i!=-1; i=nex[i]) 20 if (st[i]==nw) 21 { 22 f[i]=max(f[i],s); 23 return; 24 } 25 st[++len]=nw; f[len]=s; 26 nex[len]=p[x]; p[x]=len; 27 } 28 } h[2]; 29 int n,m,cas,p,ex,ey; 30 int a[15][15],b[15],v[15]; 31 32 void get(ll st) 33 { 34 for (int i=m; i>=0; i--) 35 { 36 b[i]=st&7; 37 st>>=3; 38 } 39 } 40 41 ll put() 42 { 43 memset(v,255,sizeof(v)); v[0]=0; 44 ll st=0; int t=0; 45 for (int i=0; i<=m; i++) 46 { 47 if (v[b[i]]==-1) v[b[i]]=++t; 48 b[i]=v[b[i]]; 49 st<<=3; st|=b[i]; 50 } 51 return st; 52 } 53 54 void shift() 55 { 56 for (int i=m;i; i--) b[i]=b[i-1]; 57 b[0]=0; 58 } 59 60 void dp(int i,int j) 61 { 62 for (int k=1; k<=h[1-p].len; k++) 63 { 64 get(h[1-p].st[k]); 65 int x=b[j],y=b[j-1]; 66 if (i==1&&j==1) 67 { 68 if (i
poj3133
1 #include2 #include 3 #include 4 5 const int maxl=1100010; 6 using namespace std; 7 struct node{ 8 int len,f[maxl],st[maxl]; 9 void clr() 10 { 11 for (int i=1; i<=len; i++) f[st[i]]=-1; 12 len=0; 13 } 14 void push(int nw,int s) 15 { 16 if (f[nw]==-1) 17 { 18 st[++len]=nw; 19 f[nw]=s; 20 } 21 else f[nw]=min(f[nw],s); 22 } 23 } h[2]; 24 int n,m,cas,p; 25 int a[15][15],b[15]; 26 27 void get(int st) 28 { 29 for (int i=m; i>=0; i--) 30 { 31 b[i]=st&3; 32 st>>=2; 33 } 34 } 35 36 int put() 37 { 38 int st=0; 39 for (int i=0; i<=m; i++) {st<<=2; st|=b[i];} 40 return st; 41 } 42 43 void shift() 44 { 45 for (int i=m;i; i--) b[i]=b[i-1]; 46 b[0]=0; 47 } 48 49 void dp(int i,int j) 50 { 51 for (int k=1; k<=h[1-p].len; k++) 52 { 53 get(h[1-p].st[k]); 54 int x=b[j],y=b[j-1],st=h[1-p].st[k]; 55 if (a[i][j]!=1) 56 { 57 if (!a[i][j]&&!x&&!y) h[p].push(st,h[1-p].f[st]); 58 else if (a[i][j]>1) 59 { 60 if (((x&&!y)||(!x&&y))&&(x+y==a[i][j])) {b[j]=b[j-1]=0; h[p].push(put(),h[1-p].f[st]+1);} 61 else if (!x&&!y) 62 { 63 if (a[i][j+1]==a[i][j]||a[i][j+1]==1) {b[j]=a[i][j]; b[j-1]=0; h[p].push(put(),h[1-p].f[st]+1);} 64 if (a[i+1][j]==a[i][j]||a[i+1][j]==1) {b[j-1]=a[i][j]; b[j]=0; h[p].push(put(),h[1-p].f[st]+1);} 65 } 66 } 67 continue; 68 } 69 if (x&&y&&x==y) {b[j]=b[j-1]=0; h[p].push(put(),h[1-p].f[st]+1);} 70 else if ((x&&!y)||(!x&&y)) 71 { 72 int r=x+y; 73 if (a[i][j+1]==1||a[i][j+1]==r) {b[j]=r; b[j-1]=0; h[p].push(put(),h[1-p].f[st]+1);} 74 if (a[i+1][j]==1||a[i+1][j]==r) {b[j-1]=r; b[j]=0; h[p].push(put(),h[1-p].f[st]+1);} 75 } 76 else if (!x&&!y) 77 { 78 if (a[i][j+1]&&a[i+1][j]) 79 { 80 if (a[i][j+1]==1&&a[i+1][j]==1) 81 { 82 b[j]=b[j-1]=2; h[p].push(put(),h[1-p].f[st]+1); 83 b[j]=b[j-1]=3; h[p].push(put(),h[1-p].f[st]+1); 84 } 85 else if (a[i][j+1]==2&&a[i+1][j]==1||a[i][j+1]==1&&a[i+1][j]==2||a[i+1][j]==2&&a[i][j+1]==2) {b[j]=b[j-1]=2; h[p].push(put(),h[1-p].f[st]+1);} 86 else if (a[i][j+1]==3&&a[i+1][j]==1||a[i][j+1]==1&&a[i+1][j]==3||a[i+1][j]==3&&a[i][j+1]==3) {b[j]=b[j-1]=3; h[p].push(put(),h[1-p].f[st]+1);} 87 } 88 h[p].push(st,h[1-p].f[st]); 89 } 90 } 91 } 92 93 int main() 94 { 95 h[1].len=h[0].len=0; 96 memset(h[0].f,255,sizeof(h[0].f)); 97 memset(h[1].f,255,sizeof(h[1].f)); 98 scanf("%d%d",&n,&m); 99 while (n&&m)100 {101 memset(a,0,sizeof(a));102 for (int i=1; i<=n; i++)103 {104 for (int j=1; j<=m; j++)105 {106 scanf("%d",&a[i][j]);107 if (a[i][j]==0||a[i][j]==1) a[i][j]^=1;108 }109 }110 h[0].push(0,0); p=0;111 for (int i=1; i<=n; i++)112 {113 p^=1; h[p].clr();114 for (int k=1; k<=h[1-p].len; k++)115 {116 get(h[1-p].st[k]); int st=h[1-p].st[k]; shift();117 h[p].push(put(),h[1-p].f[st]);118 }119 for (int j=1; j<=m; j++)120 {121 p^=1; h[p].clr();122 dp(i,j);123 }124 }125 int ans=0;126 for (int i=1; i<=h[p].len; i++)127 {128 int st=h[p].st[i];129 ans+=h[p].f[st];130 }131 if (ans>0) ans-=2;132 printf("%d\n",ans);133 h[1].clr(); h[0].clr();134 scanf("%d%d",&n,&m);135 }136 return 0;137 }
hdu4285
1 #include2 #include 3 #include 4 typedef long long ll; 5 const int ha=30007; 6 const int maxl=300010; 7 const int mo=1000000007; 8 using namespace std; 9 struct node{ 10 int p[ha],nex[maxl],len,f[maxl]; 11 ll st[maxl]; 12 void clr() 13 { 14 len=0; memset(p,255,sizeof(p)); 15 } 16 void push(ll nw,int s) 17 { 18 int x=nw%ha; 19 for (int i=p[x];i!=-1; i=nex[i]) 20 if (st[i]==nw) 21 { 22 f[i]=(f[i]+s)%mo; 23 return; 24 } 25 st[++len]=nw; f[len]=s; 26 nex[len]=p[x]; p[x]=len; 27 } 28 } h[2]; 29 int n,m,cas,p,t; 30 int a[15][15],b[15],v[15]; 31 32 void get(ll st) 33 { 34 b[m+1]=st&63; st>>=6; 35 for (int i=m; i>=0; i--) 36 { 37 b[i]=st&7; 38 st>>=3; 39 } 40 } 41 42 ll put() 43 { 44 memset(v,255,sizeof(v)); v[0]=0; 45 ll st=0; int t=0; 46 for (int i=0; i<=m; i++) 47 { 48 if (v[b[i]]==-1) v[b[i]]=++t; 49 b[i]=v[b[i]]; 50 st<<=3; st|=b[i]; 51 } 52 st<<=6; st|=b[m+1]; 53 return st; 54 } 55 56 void shift() 57 { 58 for (int i=m;i; i--) b[i]=b[i-1]; 59 b[0]=0; 60 } 61 62 bool check(int j) 63 { 64 bool ff=1; 65 for (int i=0; i
矩阵乘法加速插头dp的几题一直想做，抽时间要补一下