[ACM] POJ2353 POJ3612解题报告

119 Replies

POJ2353
穷逼DP时间复杂度O(n*m*m), 我想的就是这个..
牛逼DP时间复杂度O(n*m), 每一个room的状态都只能由左下右三个room决定, 从底向上双向递归..

POJ3612
把dp[i][h]分成两部分求解, 两部分可以分别以O(100)预处理, 求dp[i][h]是O(1), 所以整个复杂度只有O(n*100), 很棒
引用牛kevin0602的讲解(他的博客已经进不去了.. 不知为何)

先分h’大于h和小于h两种情况，这方程可写为f(n, h) = (H[i]-h)^2 + min { -C*h + min { f(n-1, h’)+C*h’ } (for h’ >= h),C*h + min { f(n-1, h’)-C*h’ } (for h’ < h) }，这样就把h’放在一起了，现在定义low(n, h) := min over h' >= h { f(n, h’)+C*h’ }，high(n, h) := min over h’ < h { f(n, h')-C*h' }，则可方程进一步写为f(n, h) = (H[i]-h)^2 + min { -C*h+low(n-1, h), C*h+high(n-1, h) }。在计算第n个电线杆的时候，low(n-1, h)和 high(n-1, h)用双重DP的方法可以在O(100)*3的时间内算出，则总时间复杂度为O(N*100)。

双向DP有点类似双向BFS, 两次BFS后可以O(1)求通过某点的入口-出口路径, 这两个题每一个状态都是可以表示成从两个状态比较来. 以后遇到类似的题目要警觉一下.. 或许还有三向之类的衍生..

代码:

2353
[cpp]
#include <stdio.h>

int main() {
int M,N;
scanf("%d%d",&N,&M);
int dp[101][501];
int path[101][501]; //0: down 1: left 2: right
int a[101][501];

for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
scanf("%d",a[i]+j);

for(int i=1;i<=M;i++) {
dp[0][i]=0;
path[0][i]=-1;
}

for(int i=1;i<=N;i++) {
for(int j=1;j<=M;j++) {
dp[i][j]=dp[i-1][j]+a[i][j];
path[i][j]=0;
}
for(int j=2;j<=M;j++) {
int foo=dp[i][j-1]+a[i][j];
if(foo<dp[i][j]) {
dp[i][j]=foo;
path[i][j]=1;
}
}
for(int j=M-1;j>=1;j–) {
int foo=dp[i][j+1]+a[i][j];
if(foo<dp[i][j]) {
dp[i][j]=foo;
path[i][j]=2;
}
}
}

/*for(int i=N;i>=1;i–) {
for(int j=1;j<=M;j++)
printf("%d ",path[i][j]);
printf("\n");
}*/

dp[N][0]=0x7fffffff;
int p=0;
for(int i=1;i<=M;i++)
if(dp[N][i]<dp[N][p])
p=i;

int __path[30000];
int __n=0;
int *__p=path[N]+p;
while(*__p!=-1) {
__path[__n++]=p;
switch(*__p) {
case 0:
__p-=501;
break;
case 1:
__p–;
p–;
break;
case 2:
__p++;
p++;
break;
}
}

for(int i=__n-1;i>=0;i–)
printf("%d\n",__path[i]);

return 0;
}
[/cpp]

3612
[cpp]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
int N,C,H[100001];
scanf("%d%d",&N,&C);
for(int i=1;i<=N;i++)
scanf("%d",H+i);

int *dp=(int *)malloc(sizeof(int)*101);
memset(dp,0,sizeof(int)*101);

for(int i=1;i<=N;i++) {
int d[101],u[101],min;

min=0x7fffffff;
for(int k=1;k<=100;k++) {
if(dp[k]-C*k<min)
min=dp[k]-C*k;
d[k]=min;
}

min=0x7fffffff;
for(int k=100;k>=1;k–) {
if(dp[k]+C*k<min)
min=dp[k]+C*k;
u[k]=min;
}

int *__dp=(int *)malloc(sizeof(int)*101);
for(int k=1;k<H[i];k++)
__dp[k]=1E9;
for(int k=H[i];k<=100;k++) {
int uv=u[k]-C*k;
int dv=d[k]+C*k;
__dp[k]=uv<dv?uv:dv;
__dp[k]+=(k-H[i])*(k-H[i]);
}

free(dp);
dp=__dp;
}

int result=0x7ffffff;
for(int i=1;i<=100;i++)
result=dp[i]<result?dp[i]:result;
printf("%d\n",result);
return 0;
}
[/cpp]

119 thoughts on “[ACM] POJ2353 POJ3612解题报告”

Leave a Reply

Your email address will not be published. Required fields are marked *