[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”

  6. muB

    Осознанный гемблинг — это стратегия к азартным сессиям, базирующийся на самоограничении и понимании рисков.
    Она включает осознанное лимитирование продолжительности и бюджета на игру.
    Любой игрок обязан предварительно определять лимиты ставок и неукоснительно их придерживаться.
    https://kart1na.ru/entry/336-otzyvy-realnykh-igrokov-o-randx-casino-plyusy-problemy-rekomendatsii/

    Reply ↓
  7. duttymub

    Осознанный подход к гемблингу — это стиль поведения, при которой азарт являются способом досуга, а не средством поправить финансовое положение.
    Она базируется на управлении длительностью и бюджетом, а ещё на осознании своих границ.
    https://ipcfms.ru/read/398-v-pogone-za-vnutrennim-ravnovesiem-podborka-praktik-protiv-ustalosti-i-trevogi.html

    Reply ↓
  8. muB

    Осознанный гемблинг — это подход к игровым развлечениям, основанный на самоограничении и осознании последствий.
    Эта концепция включает добровольное ограничение времени и расходов на процесс.
    Любой участник должен предварительно устанавливать пределы потерь и строго их придерживаться.
    https://pilot-club.ru/info/2026-07-09-svetovoy-proryv-v-bolsheokhtinskom-skvere-osveshchyonnost-vyrosla-vchetvero/

    Reply ↓
  15. muB

    Осознанный гемблинг — это принцип к азартным сессиям, основанный на контроле и понимании рисков.
    Эта концепция подразумевает добровольное ограничение времени и бюджета на игру.
    Любой участник должен заранее устанавливать пределы потерь и строго их соблюдать.
    https://rosotels.ru/detail/2026-06-27-valentina-matvienko-otsenila-nasledie-sergeya-ivanova.htm

    Reply ↓
  16. muB

    Responsible gambling is a collection of practices that guarantee gambling remains a recreational activity rather than a source of stress or loss.
    It involves establishing personal boundaries on duration and money spent, as well as recognising the signs of harmful behaviour.
    In essence, responsible gambling encourages informed choices and helps players to keep control over their playing activities.
    https://legicon-pravo.ru/data/3204-laureaty-respublikanskoy-premii-v-sfere-kultury-iskusstva-i-literatury-2026.html

    Reply ↓
  18. muB

    Ответственная игра — это стратегия к казино, базирующийся на самоограничении и понимании последствий.
    Эта концепция включает осознанное лимитирование времени и расходов на игру.
    Каждый участник должен заранее определять лимиты потерь и неукоснительно их соблюдать.
    https://legicon-pravo.ru/data/3393-khoroshie-nastroenie-ot-chetveronogikh-druzey-kogda-pitomtsy-iz-ekaterinburga-zastavlyayut-smeyatsya.html

    Reply ↓
  25. muB

    Prudent betting is a collection of practices that ensure betting stays a form of entertainment instead of a means of stress or loss.
    It involves establishing personal boundaries on time and money spent, as well as recognising the indicators of harmful behaviour.
    In essence, responsible gambling promotes conscious choices and helps players to maintain balance over their playing activities.
    https://tltrock.ru/material/2026-06-19-kalmytskie-pedagogi-zavershili-obuchenie-v-pervom-kazachem-universitete.html

    Reply ↓
  27. muB

    Осознанный гемблинг — это подход к игровым развлечениям, базирующийся на контроле и осознании рисков.
    Она подразумевает осознанное ограничение времени и бюджета на игру.
    Любой участник обязан заранее определять пределы ставок и строго их придерживаться.
    https://palmertek.ru/article/1340/

    Reply ↓
  34. видео страпон

    Сайты для 18+ способны выступать каналом интимного просвещения, помогая пользователям осознавать свою природу.
    Они дают возможность изучать многообразие подходов в защищённом пространстве, уменьшая риск реальных осложнений.
    В отношениях совместный интерес способен укреплять доверие и становиться основанием для честного разговора о фантазиях и предпочтениях.
    видео минет горловой

    Reply ↓
  35. muB

    Prudent betting is a collection of principles that ensure gambling stays a recreational activity rather than a source of financial strain.
    It involves establishing personal boundaries on duration and money spent, as well as being aware of the indicators of problematic behaviour.
    In essence, responsible gambling promotes informed choices and helps players to keep balance over their gaming activities.
    https://dvery35.ru/article/4163-sk-rossii-vnov-treboval-uzhestochit-nakazanie-yuridicheskikh-lits.html

    Reply ↓
  36. muB

    Ответственная игра — это принцип к азартным сессиям, базирующийся на самоограничении и осознании рисков.
    Она включает добровольное лимитирование продолжительности и денег на игру.
    Любой игрок должен заранее определять лимиты ставок и неукоснительно их придерживаться.
    https://petlover.nash-mihailovsk.ru/W0iN6WyGQD4L/

    Reply ↓
  39. muB

    Осознанный гемблинг — это стратегия к игровым развлечениям, базирующийся на контроле и осознании рисков.
    Она предполагает добровольное лимитирование времени и денег на игру.
    Каждый участник обязан заранее устанавливать пределы потерь и неукоснительно их придерживаться.
    https://petlover.nash-mihailovsk.ru/2GyBOJ4PY8qy/

    Reply ↓
  40. muB

    Для воспитателей повышение компетенций являются критическими, поскольку такое обучение способствуют внедрять новейшие методики.
    В результате таким занятиям педагоги имеют шанс адаптироваться к меняющимся условиям образования.
    Следовательно существенно повышается качество обучения, что благотворно отражается на учениках и их успеваемость.
    https://v-tagile.ru/obschestvo-noyabr-5/neskuchnaya-botanika-kak-zastavit-shestiklassnikov-polyubit-pestiki-i-tychinki

    Reply ↓
  48. muB

    Осознанный гемблинг — это принцип к казино, базирующийся на контроле и понимании рисков.
    Эта концепция включает добровольное ограничение времени и бюджета на процесс.
    Каждый игрок обязан заранее определять пределы ставок и неукоснительно их соблюдать.
    https://businessman.fashionvipclub.ru/3BoTgw47spyZ/

    Reply ↓
  49. заказать кроссовки Дольче Габбана

    Кеды D&G — это идеальный микс неповторимой элегантности и новейших направлений.
    Ключевой чертой данных моделей считается запоминающийся дизайн с использованием дорогих тканей и узнаваемой отделки.
    Эти кроссовки великолепно смотрятся для ежедневной эксплуатации, добавляя в стиль штрих гламура.
    https://nanmed.ru/read/4161-trendovye-letnie-sarafany-2024-bolee-30-modeley-kotorye-stoit-uspet-nadet-do-kontsa-sezona/

    Reply ↓
  50. muB

    Разумное отношение к азарту — это стратегия к казино, основанный на самоограничении и понимании последствий.
    Она предполагает осознанное лимитирование времени и денег на процесс.
    Любой игрок обязан заранее устанавливать лимиты потерь и строго их придерживаться.
    https://a3.megakazan.ru/jrJyhapLdNu9/

    Reply ↓

Leave a Reply

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