[ACM] POJ 2430 解题报告, 状态压缩DP, 奶牛你太懒了..

从左到右DP, 存储哪里有奶牛以后排序, 同一个x坐标的上下奶牛合并.. 0没有 1上 2下 3都有
随着奶牛的位置x从左到右DP, 需要记录的状态是dp[i][p][k], p是在x处的奶牛圈起来的方式, 我记的是 0没圈(这就初始状态可能) 1圈上 2圈下 3两个一起圈 4两个分开圈, 记录每个可能的k和对应的面积最小值
状态转移比较麻烦.. 我是又分两个状态之间的圈圈怎样互相结合来枚举, 0不结合 1上边延伸出去 2下边 3两边一起延伸 4两边分开延伸. 应该还有更巧妙的方法.. 不想再碰这题了
172ms 直接大数组20M内存..代码点下面

[cpp]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int adoptable(int p,int q) {
if(p==3||p==4)
return q==p?0:-1;
if(p==1||p==2) {
if(q==p)
return 0;
if(q==4)
return 1;
return -1;
}
//p==0;
return q==0?0:q==4?2:1;
}

int ifAddK(int p0,int p1,int stretch) {
if(adoptable(stretch,p0)==-1)
return -1;
return adoptable(stretch,p1);
}

int cmp(const void *_a, const void *_b) {
int a=*(int *)_a,b=*(int *)_b;
return (a>>3)-(b>>3);
}

int main() {
int N,K,B;
scanf("%d%d%d",&N,&K,&B);

int map[1001];
for(int i=1;i<=N;i++)
map[i]=-1;
int mapN=0;
for(int i=1;i<=N;i++) {
int u,pos;
scanf("%d%d",&u,&pos);
int j;
for(j=1;j<=mapN;j++)
if( (map[j]>>3)==pos )
break;
if(j>mapN) {
map[j]= (pos<<3)|u;
mapN++;
}
else
map[j]|=u;
}

qsort(map+1,mapN,sizeof(int),cmp);

int (*dp)[5][1001];
dp=(int (*)[5][1001])malloc(sizeof(int)*1001*5*1001);
memset(dp[0],0xff,sizeof(dp[0]));
dp[0][0][0]=0;
map[0]=0;
for(int i=1;i<=mapN;i++) {
memset(dp[i],0xff,sizeof(dp[0]));

for(int p0=0;p0<=4;p0++) //Statu of last
for(int p1=0;p1<=4;p1++) // This state
{
if(p1!=4 && (p1|(map[i]&3))!=p1)
continue;
for(int stretch=0;stretch<=4;stretch++) //which side stretching
{
int addK=ifAddK(p0,p1,stretch);
if(addK==-1)
continue;

int addC=(map[i]>>3)-(map[i-1]>>3)-1;
addC*=(stretch==1||stretch==2)?1:stretch==0?0:2;
addC+=(p1==0)?0:(p1==1||p1==2)?1:2;
for(int k=0;k<=K;k++) {
int k1=k+addK;
if(k1>K)
break;
if(dp[i-1][p0][k]==-1)
continue;
if(dp[i][p1][k1]==-1||dp[i][p1][k1]>dp[i-1][p0][k]+addC)
dp[i][p1][k1]=dp[i-1][p0][k]+addC;
}
}
}
}
int result=2e9;
for(int p=0;p<=4;p++)
result=dp[mapN][p][K]!=-1&&dp[mapN][p][K]<result?dp[mapN][p][K]:result;
printf("%d\n",result);
return 0;
}
[/cpp]

Asher.GG

git gut together

[ACM] POJ 2430 解题报告, 状态压缩DP, 奶牛你太懒了..

102 thoughts on “[ACM] POJ 2430 解题报告, 状态压缩DP, 奶牛你太懒了..”

Leave a Reply Cancel reply