ZJU1027, 1074, 1076, 1093, 1100
TurtleIzzy
posted @ 2008年6月13日 02:23
in ZOJ
with tags
DP ZJU ZOJ 程序 1027 1074 1076 1093 1100
, 2621 阅读
1027是典型的两个串的DP，其实就是LCS的增强版，LCS相当于题中的表只有相等的元素值为1，其余都是0。于是按照LCS的方程做就可以了。关键问题在于边界，一定要先处理好边界（也就是一开头就是空格）的情况，这样DP才对。
#include <cstdio>
#include <cstring>
const int table[5][5]=
{{5, -1, -2, -1, -3},
{-1, 5, -3, -2, -4},
{-2, -3, 5, -2, -2},
{-1, -2, -2, 5, -1},
{-3, -4, -2, -1, 0}};
int cases, f[101][101];
inline int max(int a, int b)
{
return a>b?a:b;
}
int main()
{
FILE *in = fopen("z_1027.in", "r");
fscanf(in, "%d", &cases);
for (int casess=0;casess<cases;casess++)
{
int l[2];
char s[2][101];
memset(s, 0, sizeof(s));
fscanf(in, "%d %s\n", &l[0], &s[0]);
fscanf(in, "%d %s\n", &l[1], &s[1]);
for (int j=0;j<2;j++)
for (int i=l[j]-1;i>=0;i--)
s[j][i+1]=s[j][i];
for (int j=0;j<2;j++)
for (int i=1;i<=l[j];i++)
switch (s[j][i])
{
case 'A':
s[j][i]=0;
break;
case 'C':
s[j][i]=1;
break;
case 'G':
s[j][i]=2;
break;
case 'T':
s[j][i]=3;
break;
}
memset(f, 0, sizeof(f));
for (int i=1;i<=l[1];i++)
f[0][i]=f[0][i-1] + table[4][s[1][i]];
for (int i=1;i<=l[0];i++)
f[i][0]=f[i-1][0] + table[s[0][i]][4];
for (int i=1;i<=l[0];i++)
for (int j=1;j<=l[1];j++)
{
f[i][j]=max(f[i-1][j-1]+table[s[0][i]][s[1][j]], f[i-1][j]+table[s[0][i]][4]);
f[i][j]=max(f[i][j], f[i][j-1]+table[4][s[1][j]]);
}
printf("%d\n", f[l[0]][l[1]]);
}
}
#include <cstring>
const int table[5][5]=
{{5, -1, -2, -1, -3},
{-1, 5, -3, -2, -4},
{-2, -3, 5, -2, -2},
{-1, -2, -2, 5, -1},
{-3, -4, -2, -1, 0}};
int cases, f[101][101];
inline int max(int a, int b)
{
return a>b?a:b;
}
int main()
{
FILE *in = fopen("z_1027.in", "r");
fscanf(in, "%d", &cases);
for (int casess=0;casess<cases;casess++)
{
int l[2];
char s[2][101];
memset(s, 0, sizeof(s));
fscanf(in, "%d %s\n", &l[0], &s[0]);
fscanf(in, "%d %s\n", &l[1], &s[1]);
for (int j=0;j<2;j++)
for (int i=l[j]-1;i>=0;i--)
s[j][i+1]=s[j][i];
for (int j=0;j<2;j++)
for (int i=1;i<=l[j];i++)
switch (s[j][i])
{
case 'A':
s[j][i]=0;
break;
case 'C':
s[j][i]=1;
break;
case 'G':
s[j][i]=2;
break;
case 'T':
s[j][i]=3;
break;
}
memset(f, 0, sizeof(f));
for (int i=1;i<=l[1];i++)
f[0][i]=f[0][i-1] + table[4][s[1][i]];
for (int i=1;i<=l[0];i++)
f[i][0]=f[i-1][0] + table[s[0][i]][4];
for (int i=1;i<=l[0];i++)
for (int j=1;j<=l[1];j++)
{
f[i][j]=max(f[i-1][j-1]+table[s[0][i]][s[1][j]], f[i-1][j]+table[s[0][i]][4]);
f[i][j]=max(f[i][j], f[i][j-1]+table[4][s[1][j]]);
}
printf("%d\n", f[l[0]][l[1]]);
}
}
1074是最大子矩阵，这范围太小了，随便枚举就能过。如果范围大一些可以用悬线＋单调栈来做。
#include <cstdio>
int s[100][100], n, sum, a[100][100];
inline int max(int a, int b)
{
return a>b?a:b;
}
int getsum(int x1, int y1, int x2, int y2)
{
if (x1!=0)
if (y1!=0) return s[x2][y2] - (s[x1-1][y2]+s[x2][y1-1]-s[x1-1][y1-1]);
else return s[x2][y2] - s[x1-1][y2];
else
if (y1!=0) return s[x2][y2] - s[x2][y1-1];
else return a[0][0];
}
int main()
{
FILE* in = fopen("z_1074.in", "r");
fscanf(in, "%d", &n);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
fscanf(in, "%d", &a[i][j]);
if (i!=0)
if (j!=0) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
else s[i][j] = s[i-1][0] + a[i][j];
else
if (j!=0) s[0][j] = s[0][j-1] + a[i][j];
else s[0][0]=a[0][0];
}
for (int i1=0;i1<n;i1++)
for (int j1=0;j1<n;j1++)
for (int i2=i1;i2<n;i2++)
for (int j2=j1;j2<n;j2++)
sum = max(getsum(i1, j1, i2, j2), sum);
printf("%d\n", sum);
}
int s[100][100], n, sum, a[100][100];
inline int max(int a, int b)
{
return a>b?a:b;
}
int getsum(int x1, int y1, int x2, int y2)
{
if (x1!=0)
if (y1!=0) return s[x2][y2] - (s[x1-1][y2]+s[x2][y1-1]-s[x1-1][y1-1]);
else return s[x2][y2] - s[x1-1][y2];
else
if (y1!=0) return s[x2][y2] - s[x2][y1-1];
else return a[0][0];
}
int main()
{
FILE* in = fopen("z_1074.in", "r");
fscanf(in, "%d", &n);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
fscanf(in, "%d", &a[i][j]);
if (i!=0)
if (j!=0) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
else s[i][j] = s[i-1][0] + a[i][j];
else
if (j!=0) s[0][j] = s[0][j-1] + a[i][j];
else s[0][0]=a[0][0];
}
for (int i1=0;i1<n;i1++)
for (int j1=0;j1<n;j1++)
for (int i2=i1;i2<n;i2++)
for (int j2=j1;j2<n;j2++)
sum = max(getsum(i1, j1, i2, j2), sum);
printf("%d\n", sum);
}
1076是相当于找出最多的不相交区间，先按右端点排序，然后就是个LIS。可以枚举起点直接贪心选择也可以DP。这题目的关键似乎在按照右端点排序这一步，因为我原来按照左端点排序就WA，改成右端点就AC，真奇怪…我觉得是等价的阿…哦，还有一个要注意的是如果DP应该把数组初始值都设为1。程序就不贴了，太丑陋了。
1093是三维的LIS的加强，而且可以旋转。旋转处理起来比较麻烦，于是干脆就把所有立方体都转好了加到里头去，然后规定不能旋转。这样就是个一般的DP了，按照第一维排序然后就很容易写方程了。一些小细节就是要事先把三维排个序，然后规定一下长宽高分别是哪个维，这样判断起来也方便DP起来也方便。
//AC
#include <cstdio>
#include <cstring>
#include <cstdlib>
int block[100][3], blocknum, n, f[100], max=0;
int cmp(const void *a, const void *b)
{
int aa[3], bb[3];
memcpy(aa, (int *)a, sizeof(aa));
memcpy(bb, (int *)b, sizeof(bb));
return (bb[0]-aa[0]);
}
void swap(int &a, int &b)
{
int t=a; a=b; b=t;
}
void insert(int a, int b, int c)
{
blocknum++;
block[blocknum][0]=a;
block[blocknum][1]=b;
block[blocknum][2]=c;
}
int main()
{
FILE *in = fopen("z_1093.in", "r");
int cases=0;
while (1)
{
cases++;
fscanf(in, "%d", &n);
if (n==0) return 0;
memset(block, 0, sizeof(block));
blocknum=0;
memset(block[0], 10, sizeof(block[0]));
for (int i=0;i<n;i++)
{
int a, b, c;
fscanf(in, "%d%d%d", &a, &b, &c);
if (a>b) swap(a, b);
if (b>c) swap(b, c);
if (a>b) swap(a, b);
insert(a, b, c);
if (a!=b)
{
if (c!=a) insert(b, c, a);
if (c!=b) insert(a, c, b);
}
else
if (b!=c) insert(a, c, b);
}
qsort(block, blocknum+1, sizeof(block[0]), cmp);
memset(f, 0, sizeof(f));
max=0;
for (int i=1;i<=blocknum;i++)
for (int j=0;j<i;j++)
if (block[i][0]<block[j][0]&&block[i][1]<block[j][1]&&f[i]<f[j]+block[i][2])
{
f[i] = f[j] + block[i][2];
max = f[i]>max?f[i]:max;
}
printf("Case %d: maximum height = %d\n", cases, max);
}
}
#include <cstdio>
#include <cstring>
#include <cstdlib>
int block[100][3], blocknum, n, f[100], max=0;
int cmp(const void *a, const void *b)
{
int aa[3], bb[3];
memcpy(aa, (int *)a, sizeof(aa));
memcpy(bb, (int *)b, sizeof(bb));
return (bb[0]-aa[0]);
}
void swap(int &a, int &b)
{
int t=a; a=b; b=t;
}
void insert(int a, int b, int c)
{
blocknum++;
block[blocknum][0]=a;
block[blocknum][1]=b;
block[blocknum][2]=c;
}
int main()
{
FILE *in = fopen("z_1093.in", "r");
int cases=0;
while (1)
{
cases++;
fscanf(in, "%d", &n);
if (n==0) return 0;
memset(block, 0, sizeof(block));
blocknum=0;
memset(block[0], 10, sizeof(block[0]));
for (int i=0;i<n;i++)
{
int a, b, c;
fscanf(in, "%d%d%d", &a, &b, &c);
if (a>b) swap(a, b);
if (b>c) swap(b, c);
if (a>b) swap(a, b);
insert(a, b, c);
if (a!=b)
{
if (c!=a) insert(b, c, a);
if (c!=b) insert(a, c, b);
}
else
if (b!=c) insert(a, c, b);
}
qsort(block, blocknum+1, sizeof(block[0]), cmp);
memset(f, 0, sizeof(f));
max=0;
for (int i=1;i<=blocknum;i++)
for (int j=0;j<i;j++)
if (block[i][0]<block[j][0]&&block[i][1]<block[j][1]&&f[i]<f[j]+block[i][2])
{
f[i] = f[j] + block[i][2];
max = f[i]>max?f[i]:max;
}
printf("Case %d: maximum height = %d\n", cases, max);
}
}
1100是个状态压缩DP。按列DP，用二进制数s表示最后一列的状态（是有石头还是没有），然后DFS往上头放。这复杂度是指数级的，不过n不大没关系。我觉得程序写得异常简洁，对于一贯代码累赘的我来说…
//AC 0.07s
#include <cstdio>
#include <cstring>
long long f[2][3000], w, h;
void dfs(int pos, int cur, int next, int org)
{
if (cur==(1<<h)-1)
{
if (pos!=w) f[pos&1][next] += f[(pos-1)&1][org];
else f[pos&1][cur] += f[(pos-1)&1][org];
return;
}
for (int i=0;i<h;i++)
if ((cur&(1<<i))==0)
{
//yoko
if ((next&(1<<i))==0&&pos!=w) dfs(pos, cur+(1<<i), next+(1<<i), org);
//tate
if (i<h-1&&(cur&(1<<(i+1)))==0) dfs(pos, cur+(1<<i)+(1<<(i+1)), next, org);
return;
}
}
int main()
{
FILE *in = fopen("z_1100.in", "r");
while (1)
{
fscanf(in, "%d%d", &w, &h);
if (w==0) return 0;
memset(f, 0, sizeof(f));
f[0][0]=1;
for (int i=1;i<=w;i++)
{
memset(f[i&1], 0, sizeof(f[i&1]));
for (int j=0;j<(1<<h);j++)
if (f[(i-1)&1][j])
dfs(i, j, 0, j);
}
printf("%lld\n", f[w&1][(1<<h)-1]);
}
}
#include <cstdio>
#include <cstring>
long long f[2][3000], w, h;
void dfs(int pos, int cur, int next, int org)
{
if (cur==(1<<h)-1)
{
if (pos!=w) f[pos&1][next] += f[(pos-1)&1][org];
else f[pos&1][cur] += f[(pos-1)&1][org];
return;
}
for (int i=0;i<h;i++)
if ((cur&(1<<i))==0)
{
//yoko
if ((next&(1<<i))==0&&pos!=w) dfs(pos, cur+(1<<i), next+(1<<i), org);
//tate
if (i<h-1&&(cur&(1<<(i+1)))==0) dfs(pos, cur+(1<<i)+(1<<(i+1)), next, org);
return;
}
}
int main()
{
FILE *in = fopen("z_1100.in", "r");
while (1)
{
fscanf(in, "%d%d", &w, &h);
if (w==0) return 0;
memset(f, 0, sizeof(f));
f[0][0]=1;
for (int i=1;i<=w;i++)
{
memset(f[i&1], 0, sizeof(f[i&1]));
for (int j=0;j<(1<<h);j++)
if (f[(i-1)&1][j])
dfs(i, j, 0, j);
}
printf("%lld\n", f[w&1][(1<<h)-1]);
}
}
评论 (0)