[ACM] POJ1185解题报告 状态压缩DP

199 Replies

思路和网上的都差不多, 我另外开了程序算出每一行可能的情况直接copy进 stack[] 中..耍流氓.. 看起来直观点
引用一下大牛BYVoid的思路, 不自己写了

较难看出的动态规划问题。注意到数据范围N≤100；M≤10，发现每行的宽度都不大，所以可以考虑把一行看成一个状态，表示该行的布置方案。每行的布置方案可以预先处理出，由数学知识可以算出，每行最多的布置方案数也不过60个而已。

状态设定

F[i,a,b]为前i行，第i行的方案为A[a]，第i-1行的方案为A[b]的最大炮兵数。

状态转移方程

  • F[i,a,b]=Max{ F[i-1,b,c] + P[a] }

其中c为i-2行的布置方案，a,b,c应保证互不冲突，即放置方案中炮兵都在平地上，且不会互相攻击到。

目标结果

  • Ans=Max{F[N,a,b]}

中间进行过一次错误的优化, 认为如果, 比如
画个图..

    HHPH
    PPPP
    PPPP
    HHPH  (红色代表有炮)

1001比1101少了一个1, 那么1101得出的结果至少不会比1001差, 可以剪掉1001. 比如上图的第三行, 没有炮的情况就可以省去,.我当时的想法是如果省掉第三行的炮, 放在第四行唯一的P上(其他情况也是相似),  第四行以下面临的情况就会比之前更加严峻, 从而不会得出更好的结果, 顶多一样.

但是我并没有考虑第三行能对第一行也产生影响 (造成这个错误的原因是状态压缩DP只记录近两行. 虽然没有明面上写, 但是情况已经记录在得分中了). 第三行的P不放炮, 则第一行和第四行都能放, 结果就更好了.

遗留问题, 如何才能在类的定义中实现二维数组的动态分配?

我写成这样

[cpp]public:
int *(a[60]);
State (int m=0) {
M=m;
for(int i=0;i<stackN;i++) {
a[i]=new int[stackN];
memset(a[i],0xff,sizeof(int)*stackN);
}
}[/cpp]

能够compile, 在另开的程序里也没有问题, 但是在题目中答案就不一样, 我跟踪了, 在 s[i].dp(s[i-1]) 的过程中 s[i-1].a[][] 会莫名发生改变, 实际上又没有对它进行任何操作. 值得一提的是release和debug得出的答案不一样, 根据经验应该是内存的什么问题.. 也有可能是类里动态分配内存就不对头, 因为在类中定义变量不能用new..  开学去问问看

Code: (其实是我第一次用类.. 这个问题有点绕, 于是尝试封装=D )

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

int stack[]={ 0,1,2,4,8,9,16,17,18,32,33,34,36,64,65,66,68,
72,73,128,129,130,132,136,137,144,145,146,256,
257,258,260,264,265,272,273,274,288,289,290,292,
512,513,514,516,520,521,528,529,530,544,545,546,
548,576,577,578,580,584,585,2E9 }; //All legal possibilities of assembles, denary.
int stackT[]={ 0,1,1,1,1,2,1,2,2,1,2,2,2,1,2,2,2,2,3,1,
2,2,2,2,3,2,3,3,1,2,2,2,2,3,2,3,3,2,3,3,
3,1,2,2,2,2,3,2,3,3,2,3,3,3,2,3,3,3,3,4 }; //How many 1 are there in stack.
int stackN;

class State {
private:
int M;
bool map[10];
bool ok(int foo);
public:
int a[60][60];
State (int m=0) {
M=m;
memset(a,0xff,sizeof(a));
}
void dp(State &last);
void readMap();
};

bool State::ok(int foo) {
for(int i=0;i<M;i++) {
if( ((foo>>i)&1) && map[i])
return false;
}
return true;
}

void State::readMap() {
char t;
for(int j=0;j<M;j++) {
while(1) {
t=getchar();
if(t==’H’ || t==’P’)
break;
}
map[j]= t==’H’?1:0;
}
return;
}

void State::dp(State &last) {
int temp;
for(int i=stackN-1;i>=0;i–) {
for(int j=0;j<stackN;j++) {
//if(a[i][j]==-2)
//continue;
for(int k=0;k<stackN;k++) {
if( (stack[j]|stack[k]) & stack[i] ) //Whether two states engage.
continue;
if(!ok(stack[i]))
continue;
if(last.a[j][k]<0 ) //Doesn’t exist.
continue;
temp=last.a[j][k]+stackT[i];
if(a[i][j]<temp)
a[i][j]=temp;

/* for(int h=0;h<i;h++)
if( (stack[h]|stack[i])==stack[i] )
a[h][j]=-2; */ //WRONG!
}
}
}
return;
}

int main() {
int M,N;
scanf("%d%d",&N,&M);
if(N<0 || M<0) {
printf("0\n");
return 0;
}

for(stackN=0;stack[stackN]<(1<<M);stackN++); //Set edge of stack according to the width M.

State templt(M);
State *s=new State[N+1];
for(int i=1;i<=N;i++)
s[i]=templt;
//State s[101]=State(M);
s[0].a[0][0]=0; //Initialize.

while(getchar()!=’\n’);
for(int i=1;i<=N;i++)
s[i].readMap();

for(int i=1;i<=N;i++)
s[i].dp(s[i-1]);

int max=0;
for(int i=0;i<stackN;i++)
for(int j=0;j<stackN;j++)
if(max<s[N].a[i][j])
max=s[N].a[i][j];

printf("%d\n",max);

delete []s;
return 0;
}
[/cpp]

199 thoughts on “[ACM] POJ1185解题报告 状态压缩DP”

  1. duttymub

    Ответственная игра — это стиль поведения, при которой азарт являются формой досуга, а не стремлением заработать.
    Она базируется на управлении временем и бюджетом, а также на осознании личных границ.
    https://pilot-club.ru/info/2026-07-14-trendovye-stili-krossovok-dolce-andamp-gabbana-v-2024-godu-chto-aktualno-na-ulitsakh/

    Reply ↓
  2. Jorgeepive

    Сникеры Dolce&Gabbana — представляют собой стильный микс итальянской классики и актуальных веяний.
    Главной деталью подобных кроссовок считается яркий внешний вид с использованием премиальных тканей и культовой отделки.
    Такие модели великолепно подходят для повседневной жизни, привнося в лук долю гламура.
    https://1-mk.ru/detail/478-ambush-spring-summer-2027-garderob-dlya-beskonechnogo-puti/

    Reply ↓
  3. muB

    Осознанный гемблинг — это принцип к казино, основанный на самоограничении и осознании последствий.
    Она предполагает добровольное ограничение продолжительности и бюджета на процесс.
    Любой игрок должен предварительно устанавливать лимиты потерь и строго их соблюдать.
    https://wolgograd.ru/column/2614-dua-lipa-otkryvaet-manifesto-library-literaturnyy-prizyv-k-svobode-slova/

    Reply ↓
  9. Jorgeepive

    Модели Dolce&Gabbana — это удачный союз изысканной элегантности и новейших направлений.
    Отличительной деталью подобных моделей служит запоминающийся внешний вид с сочетанием качественных тканей и узнаваемой детализации.
    Эти кроссовки прекрасно смотрятся для городской носки, добавляя в стиль нотку гламура.
    https://legicon-pravo.ru/data/3519-odno-slovo-v-perevode-mozhet-ostanovit-vash-schyot-kak-banki-zamorazhivayut-dengi-i-chto-za-etim-stoit.html

    Reply ↓
  17. Jerrybeisp

    Видеослоты — являются самые востребованные игры в онлайн-казино.
    Их главное преимущество — несложные правила, красочная визуализация и разнообразие бонусных возможностей.
    Пользователи могут выбирать слоты по тематике, количеству барабанов и уровню риска.
    https://biz.sneakersgo.ru/J5FJLjgtUHJt/

    Reply ↓
  18. Reubencresy

    Конторы предлагают шанс заключать ставки на различные турниры.
    Крайне важно выбирать проверенных букмекеров, а также тщательно изучать роспись до заключением ставки.
    Ставки могут быть интересным хобби, однако необходимо придерживаться баланс ответственной игры и ограничивать бюджет.
    https://legicon-pravo.ru/data/3617-evolyutsiya-bukmekerskogo-biznesa-ot-bumazhnykh-zapisok-do-onlayn-platform.html

    Reply ↓
  19. hasfaniyot.net

    האתר hasfaniyot.net מספק מגוון רחב של שירותים המותאמים למשתמשים הישראלי.
    בפלטפורמה תוכל למצוא חוויות ייחודיים בנושא המבוגרים באיכות גבוהה.
    האתר נותנת אפשרות קלה לחומרים הללו באמצעות שמירה על אנונימיות הגולש.
    https://hasfaniyot.net/

    Reply ↓
  25. muB

    Правила осознанной игры — это алгоритм, ориентированный на поддержание дисциплины в отношении игровым процессом и минимизацию негативных последствий.
    https://www.verdoos.com/read-blog/28274

    Reply ↓
  33. Reubencresy

    Букмекерские конторы предлагают возможность заключать пари на спортивные матчи.
    Следует выбирать надёжных операторов, а также внимательно изучать коэффициенты перед заключением ставки.
    Ставки способны быть увлекательным досугом, однако стоит придерживаться баланс осознанного подхода и контролировать бюджет.
    https://pilot-club.ru/info/2026-07-16-kak-rabotayut-koeffitsienty-matematicheskie-modeli-i-psikhologiya-stavok/

    Reply ↓

Leave a Reply

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