青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219404
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

Antenna Placement
Time Limit:1000MS? Memory Limit:65536K
Total Submit:380 Accepted:125

Description
The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them.

Obviously, it is desirable to use as few antennas as possible, but still provide coverage for each place of interest. We model the problem as follows: Let A be a rectangular matrix describing the surface of Sweden, where an entry of A either is a point of interest, which must be covered by at least one antenna, or empty space. Antennas can only be positioned at an entry in A. When an antenna is placed at row r and column c, this entry is considered covered, but also one of the neighbouring entries (c+1,r),(c,r+1),(c-1,r), or (c,r-1), is covered depending on the type chosen for this particular antenna. What is the least number of antennas for which there exists a placement in A such that all points of interest are covered?

Input
On the first row of input is a single positive integer n, specifying the number of scenarios that follow. Each scenario begins with a row containing two positive integers h and w, with 1 <= h <= 40 and 0 < w <= 10. Thereafter is a matrix presented, describing the points of interest in Sweden in the form of h lines, each containing w characters from the set ['*','o']. A '*'-character symbolises a point of interest, whereas a 'o'-character represents open space.

Output
For each scenario, output the minimum number of antennas necessary to cover all '*'-entries in the scenario's matrix, on a row of its own.

Sample Input

2
7 9
ooo**oooo
**oo*ooo*
o*oo**o**
ooooooooo
*******oo
o*o*oo*oo
*******oo
10 1
*
*
*
o
*
*
*
*
*
*

Sample Output

17
5

Source
Svenskt M?sterskap i Programmering/Norgesmesterskapet 2001

myCode:

#include? < iostream >
using ? namespace ?std;

const ? int ?INF? = ? 1 ? << ? 28 ;

int ?n,?r,?c;
int ?e[ 11 ]? = ? { 1 ,? 2 ,? 4 ,? 8 ,? 16 ,? 32 ,? 64 ,? 128 ,? 256 ,? 512 ,? 1024 } ;
char ?m[ 50 ][ 20 ];
int ?d[ 50 ][ 1024 ];
int ?b[ 20 ];
int ?cc[ 20 ];
int ?ss;

void ?Try( int ?x,? int ?s)
{
????
if ?(x? >= ?c)? {
????????
int ?k? = ? 0 ;
????????
for ?( int ?i = 0 ;?i < c;?i ++ )? {
????????????k?
+= ?b[i]? * ?e[i];
????????}

????????
if ?(d[ 0 ][k]? == ? - 1 ? || ?d[ 0 ][k]? > ?s)
????????????d[
0 ][k]? = ?s;
????????
return ?;
????}

????
if ?(m[ 0 ][x]? == ? ' o ' )? {
????????Try(x
+ 1 ,?s);
????}
? else ? if ?(m[ 0 ][x]? == ? ' * ' )? {
????????
int ?t1? = ?b[x],?t2? = ?b[x + 1 ],?t3? = ?s;
????????b[x]?
= ? 1 ;?b[x + 1 ]? = ? 1 ;?s? += ? 1 ;
????????Try(x
+ 2 ,?s);
????????b[x]?
= ?t1;?b[x + 1 ]? = ?t2;?s? = ?t3;
????????
if ?(r? != ? 1 ? || ?m[ 0 ][x]? == ? ' o ' )?Try(x + 1 ,?s);
????}
??
}


void ?DFS( int ?i,? int ?x,? int ?s)
{
????
if ?(x? >= ?c)? {
????????
int ?k? = ? 0 ;
????????
for ?( int ?j = 0 ;?j < c;?j ++ )? {
????????????k?
+= ?cc[j]? * ?e[j];
????????}

????????
if ?(d[i][k]? == ? - 1 ? || ?d[i][k]? > ?ss? + ?s)
????????????d[i][k]?
= ?ss? + ?s;
????????
return ?;
????}

????
if ?(b[x]? == ? 0 )? {
????????
if ?(m[i - 1 ][x]? == ? ' * ' )? {
????????????cc[x]?
= ? 1 ;?s? += ? 1 ;
????????????DFS(i,?x
+ 1 ,?s);
????????}
? else ? {
????????????
if ?(m[i][x]? == ? ' * ' )? {
????????????????
int ?t1? = ?cc[x],?t2? = ?cc[x + 1 ],?t3? = ?s;
????????????????cc[x]?
= ? 1 ;??cc[x + 1 ]? = ? 1 ;?s? += ? 1 ;
????????????????
if ?(b[x + 1 ]? == ? 0 ? && ?m[i - 1 ][x + 1 ]? == ? ' * ' )
????????????????????s?
+= ? 1 ;
????????????????DFS(i,?x
+ 2 ,?s);
????????????????cc[x]?
= ?t1;?cc[x + 1 ]? = ?t2;?s? = ?t3;
????????????????
if ?(i? != ?r - 1 ? || ?m[i][x]? == ? ' o ' )?DFS(i,?x + 1 ,?s);
????????????}
? else ? if ?(m[i][x]? == ? ' o ' )? {
????????????????DFS(i,?x
+ 1 ,?s);
????????????}

????????}

????}
? else ? {
????????????
if ?(m[i][x]? == ? ' * ' )? {
????????????????
int ?t1? = ?cc[x],?t2? = ?cc[x + 1 ],?t3? = ?s;
????????????????cc[x]?
= ? 1 ;??cc[x + 1 ]? = ? 1 ;?s? += ? 1 ;
????????????????
if ?(b[x + 1 ]? == ? 0 ? && ?m[i - 1 ][x + 1 ]? == ? ' * ' )
????????????????????s?
+= ? 1 ;
????????????????DFS(i,?x
+ 2 ,?s);
????????????????cc[x]?
= ?t1;?cc[x + 1 ]? = ?t2;?s? = ?t3;
????????????????
if ?(i? != ?r - 1 ? || ?m[i][x]? == ? ' o ' )?DFS(i,?x + 1 ,?s);
????????????}
? else ? if ?(m[i][x]? == ? ' o ' )? {
????????????????DFS(i,?x
+ 1 ,?s);
????????????}
??????
????}

}


void ?init()
{
????memset(d[
0 ],? - 1 ,? sizeof (d[ 0 ]));
????memset(b,?
0 ,? sizeof (b));
????Try(
0 ,? 0 );
}


void ?Solve()?
{
????
int ?i,?j,?k;
????init();
????
for ?(i = 0 ;?i < r - 1 ;?i ++ )? {
????????memset(d[i
+ 1 ],? - 1 ,? sizeof (d[i + 1 ]));
????????
for ?(k = 0 ;?k < e[c];?k ++ )? {
????????????
if ?(d[i][k]? != ? - 1 )? {
????????????????
int ?t? = ?k,?j? = ? 0 ,?kk? = ? 0 ;
????????????????memset(b,?
0 ,? sizeof (b));
????????????????memset(cc,?
0 ,? sizeof (cc));
????????????????
while ?(t? != ? 0 )? {
????????????????????b[j
++ ]? = ?t? % ? 2 ;
????????????????????t?
/= ? 2 ;
????????????????}

????????????????ss?
= ?d[i][k];
????????????????DFS(i
+ 1 ,? 0 ,? 0 );
????????????}

????????}

????}

????
int ?ans? = ?INF;
????
for ?(k = 0 ;?k < e[c];?k ++ )? {
????????
if ?(d[r - 1 ][k]? != ? - 1 ? && ?d[r - 1 ][k]? < ?ans)? {
????????????ans?
= ?d[r - 1 ][k];
????????}

????}

????cout?
<< ?ans? << ?endl;
}


int ?main()
{?
????cin?
>> ?n;
????
while ?(n -- ? != ? 0 )? {
????????cin?
>> ?r? >> ?c;
????????
for ?( int ?i = 0 ;?i < r;?i ++ )?cin? >> ?m[i];
????????Solve();
????}

????system(
" pause " );
????
return ? 0 ;
}


ghost_wei大牛的code,? 放出來供大家學習,? 用了滾動數組優化, 而且位運算用得出神入化:)
#include<iostream.h>
#include?
<fstream.h>
const?int?k2[11]={1,2,4,8,16,32,64,128,256,512,1024};
int?n,m,c[2][1024];
char?d[40][10];
inline?
void?min(int?&i,int?j)
{
????
if?(i>j)?i=j;
}

void?work()
{
????
int?i,j,km,k,e7,e8,l,t,ans;
????km
=k2[m];
????
for?(i=0;i<km;i++)?c[0][i]=100000;
????c[
0][0]=0;
????e7
=0;?e8=1;
????
for?(i=0;i<n;i++)
????
{
????????
for?(j=0;j<km;j++)?c[e8][j]=100000;
????????
for?(j=1;j<m;j++)
????????????
if?(d[i][j]=='*')
????????????????
for?(k=0;k<km;k++)
????????????????????min(c[e7][k
|k2[j]|k2[j-1]],c[e7][k]+1);
????????
for?(k=0;k<km;k++)
????????
{
????????????l
=0;?t=0;
????????????
for?(j=0;j<m;j++)?
????????????????
if?(!(k&k2[j])&&d[i][j]=='*')
????????????????
{
????????????????????l
+=k2[j];
????????????????????t
++;
????????????????}

????????????min(c[e8][l],c[e7][k]
+t);
????????}

????????e7
=e7^1;?e8=e8^1;
????}

????ans
=100000;
????
for?(k=0;k<km;k++)
????????min(ans,c[e7][k]);
????cout
<<ans<<endl;
}

int?main()
{
????
int?tc,cas,i,j;
????cin
>>tc;
????
for?(cas=1;cas<=tc;cas++)
????
{
????????cin
>>n>>m;
????????
for?(i=0;i<n;i++)
????????????
for(j=0;j<m;j++)
????????????????cin
>>d[i][j];
????????work();
????}

????
return?0;
}

posted on 2006-10-18 17:29 閱讀(2147) 評論(4)  編輯 收藏 引用 所屬分類: ACM題目

FeedBack:
# re: 狀態壓縮DP, pku3020[未登錄] 2007-04-30 11:16 Leon
Ghost的算法真是精辟,只是狀態數組定義的空間可能會不夠,代碼的line 30  回復  更多評論
  
# re: 狀態壓縮DP, pku3020 2007-06-30 10:35 姜雨生
真是太好了
以后多向你請教  回復  更多評論
  
# re: 狀態壓縮DP, pku3020[未登錄] 2008-07-02 08:22 菜鳥
大牛解釋一下這一段吧:
for (i=0;i<n;i++)
{
for (j=0;j<km;j++) c[e8][j]=100000;
for (j=1;j<m;j++)
if (d[i][j]=='*')
for (k=0;k<km;k++)
min(c[e7][k|k2[j]|k2[j-1]],c[e7][k]+1);
for (k=0;k<km;k++)
{
l=0; t=0;
for (j=0;j<m;j++)
if (!(k&k2[j])&&d[i][j]=='*')
{
l+=k2[j];
t++;
}
min(c[e8][l],c[e7][k]+t);
}
e7=e7^1; e8=e8^1;
}
  回復  更多評論
  
# re: 狀態壓縮DP, pku3020 2008-08-04 22:56 ecnu
二分匹配做的。。關鍵是狀態壓縮不會。5555...  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
      <noscript id="pjuwb"></noscript>
            <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
              <dd id="pjuwb"></dd>
              <abbr id="pjuwb"></abbr>
              亚洲精品一区二区三区福利| 制服丝袜激情欧洲亚洲| 久久精品网址| 欧美一区二区三区四区在线观看| 国产精品一区三区| 麻豆精品视频在线| 欧美成人嫩草网站| 亚洲免费在线视频| 欧美一级久久久| 亚洲国产欧美不卡在线观看 | 中日韩高清电影网| 亚洲一区二区黄| 在线成人免费观看| 亚洲免费av电影| 国产视频在线一区二区| 免费视频一区| 欧美日韩三级电影在线| 亚洲欧美日韩一区二区| 久久青青草原一区二区| 亚洲天堂男人| 久久精视频免费在线久久完整在线看| 亚洲国产精品一区| 亚洲一区二区三区免费在线观看| 国产日韩欧美一区在线 | 欧美在线黄色| 欧美精品激情blacked18| 性欧美xxxx视频在线观看| 久久久精品999| 亚洲专区在线| 快播亚洲色图| 久久精品国产91精品亚洲| 老司机午夜免费精品视频| 亚洲欧美日韩综合aⅴ视频| 久久久99国产精品免费| 国产精品99久久久久久久久| 久久偷窥视频| 久久成人精品视频| 欧美日韩精品伦理作品在线免费观看 | 欧美经典一区二区三区| 久久三级视频| 国产精品香蕉在线观看| 91久久久久久久久| 黄色小说综合网站| 亚洲欧美日韩国产一区二区三区| 亚洲精品黄网在线观看| 久久精品亚洲乱码伦伦中文| 欧美一区二区三区四区在线| 国产精品成人一区二区| 亚洲美洲欧洲综合国产一区| 亚洲激情视频| 欧美1区3d| 免费在线国产精品| 国产一区二区三区久久精品| 亚洲香蕉网站| 欧美亚洲一区三区| 国产精品入口夜色视频大尺度| 亚洲欧洲另类| 一本色道久久综合亚洲精品小说| 久久最新视频| 欧美黄色大片网站| 亚洲激情成人在线| 欧美超级免费视 在线| 欧美成人dvd在线视频| 在线精品福利| 欧美刺激性大交免费视频| 欧美国产日韩一二三区| 亚洲国产精品成人久久综合一区| 久久免费视频在线| 亚洲第一伊人| 一区二区三区高清| 国产精品高潮呻吟| 亚洲欧美在线看| 久久综合九色欧美综合狠狠| 亚洲成色999久久网站| 老司机免费视频一区二区| 亚洲国产日韩在线| 在线亚洲欧美| 国产精品视频久久久| 亚洲欧美日韩另类| 榴莲视频成人在线观看| 亚洲激情综合| 欧美视频在线观看一区| 性欧美1819sex性高清| 老巨人导航500精品| 亚洲精品免费一二三区| 国产精品福利网| 久久不射网站| 亚洲国产精品一区二区久| 一区二区三区视频观看| 国产日韩欧美在线一区| 男人的天堂亚洲在线| 99re亚洲国产精品| 久久久久国色av免费看影院| 亚洲黄色成人久久久| 国产精品乱码一区二区三区| 久久久亚洲精品一区二区三区| 亚洲国产精品高清久久久| 翔田千里一区二区| 亚洲国产精品久久久久| 欧美性猛片xxxx免费看久爱| 久久精彩视频| av不卡在线| 欧美大胆成人| 欧美一区午夜精品| 日韩视频永久免费| 国产在线观看91精品一区| 欧美激情在线| 久久久久久日产精品| aa亚洲婷婷| 亚洲国产欧美久久| 久久精品水蜜桃av综合天堂| 亚洲视频在线免费观看| 韩国女主播一区二区三区| 欧美视频一区二| 久久综合九色欧美综合狠狠| 午夜精品短视频| 宅男精品视频| 亚洲国产小视频在线观看| 久久精品国产视频| 一区二区三区四区五区在线 | 国产精品国产三级国产a| 免费成人小视频| 欧美一区不卡| 一区二区三区欧美| 亚洲欧洲综合| 欧美黑人国产人伦爽爽爽| 欧美一级黄色录像| 这里只有精品丝袜| 亚洲日韩成人| 136国产福利精品导航| 国产农村妇女精品| 国产精品视频1区| 国产精品黄色| 国产精品久久久久毛片软件| 欧美区日韩区| 欧美激情一二区| 欧美 亚欧 日韩视频在线| 久久国产视频网站| 久久国产一二区| 性欧美1819性猛交| 午夜日韩在线观看| 欧美一区二区高清| 欧美一区二区免费观在线| 亚洲综合第一| 亚洲欧美在线视频观看| 亚洲午夜在线观看| 一区二区三区 在线观看视频| 亚洲啪啪91| 亚洲美女毛片| 一本一本久久a久久精品综合妖精 一本一本久久a久久精品综合麻豆 | 韩国av一区二区三区在线观看| 国产精品一区二区三区久久| 国产精品日韩| 国产女人精品视频| 国产日本欧洲亚洲| 韩国在线视频一区| 在线欧美小视频| 99成人在线| 校园激情久久| 久久国产欧美| 久久免费视频在线| 欧美成人中文字幕| 亚洲人成网站影音先锋播放| 日韩天堂在线观看| 亚洲欧美日本国产有色| 久久爱另类一区二区小说| 快播亚洲色图| 欧美日韩综合不卡| 国产亚洲一区二区在线观看 | 亚洲精品免费一区二区三区| 亚洲一卡久久| 久久www成人_看片免费不卡| 农村妇女精品| 日韩午夜电影av| 欧美一区二区三区免费视频| 麻豆91精品91久久久的内涵| 欧美精品一区在线播放| 国产麻豆9l精品三级站| 亚洲成色精品| 亚洲午夜精品国产| 蜜桃av一区二区在线观看| 99国产精品99久久久久久粉嫩| 午夜免费久久久久| 欧美精品少妇一区二区三区| 国产精品久久久久免费a∨| 亚洲国产成人精品女人久久久 | 美脚丝袜一区二区三区在线观看| 亚洲成色777777女色窝| 午夜精品久久| 欧美精品亚洲一区二区在线播放| 国产欧美日韩综合| 99精品国产福利在线观看免费| 久久精品国产69国产精品亚洲| 91久久午夜| 久久精品国产免费观看| 国产精品久久毛片a| 亚洲毛片在线看| 久久精品九九| 在线亚洲电影| 欧美日本在线播放|