3013 - 炮兵阵地

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 128 MB

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

<br />

题目输入

文件的第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。

题目输出

文件仅在第一行包含一个整数K，表示最多能摆放的炮兵部队的数量。

输入/输出样例

输入格式

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出格式

C语言解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXR 110
#define MAXC 15
#define MAXM 70
#define max(A,B) ((A)<(B)?(B):(A))
#define CL(A) memset(A,0,sizeof(A))
#define legal(A,B) ((A)&(B))

int row, col;
int nums;
int base[MAXR];
int state[MAXM];
int soldier[MAXM];
int dp[MAXR][MAXM][MAXM];

char g[MAXR][MAXC];

int main() {
CL(base), CL(state), CL(soldier), CL(dp);
nums = 0;
scanf("%d%d",&row,&col);
for(int i = 0;i < row; i++) {
    scanf("%s",g[i]);
    for(int j = 0;j < col; j++)
        if(g[i][j]=='H')base[i] += 1<<j;
}
for(int i = 0;i <(1<<col); i++) {
    if(legal(i,i<<1) || legal(i,i<<2))continue;
    int k = i;
    while(k) {
        soldier[nums] += k&1;
        k = k >> 1;
    }
    state[nums++] = i;
}
for(int i = 0;i < nums; i++) {
    if(legal(state[i],base[0]))continue;
    dp[0][i][0]=soldier[i];
}
for(int i = 0;i < nums; i++) {
    if(legal(state[i],base[1]))continue;
    for(int j = 0;j < nums; j++) {
        if(legal(state[j],base[0]))continue;
        if(legal(state[i],state[j]))continue;
        dp[1][i][j]=max(dp[1][i][j],dp[0][j][0]+soldier[i]);
    }
}
for(int r = 2;r <= row; r++) {
    for(int i = 0;i < nums; i++) {
        if(legal(state[i],base[r]))continue;
        for(int j = 0;j < nums; j++) {
            if(legal(state[j],base[r-1]))continue;
            if(legal(state[i],state[j]))continue;
            for(int k = 0;k < nums; k++) {
              if(legal(state[k],base[r-2]))continue;
              if(legal(state[j],state[k]))continue;
              if(legal(state[i],state[k]))continue;
              dp[r][i][j]=max(dp[r][i][j],dp[r-1][j][k]+soldier[i]);
            }

        }
    }
}
    int ans = 0;
    for(int i = 0;i < nums; i++) {
        for(int j = 0;j < nums; j++) {
            ans = max(ans,dp[row-1][i][j]);
        }
    }
printf("%d\n",ans);
return 0;
}

C++解答

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 101
#define MAXK 61
#define MAXM 11
using namespace std;
int f[MAXN][MAXK][MAXK];//存结果
int g[MAXN][MAXK];//存方案
int w[MAXN][MAXK];//存当前行的炮兵个数
//string fa[MAXN][MAXK];
string s;
int n,m,tot;
void dfs(int,int,string,int);
void DP();
int zh(string x){
	int ans=0,t=1;
	for(int i=m-1;i>=0;i--){
		ans+=(x[i]-48)*t;
		t<<=1;
	}
	return ans;
} 
int main(){
	//freopen("cannon.in","r",stdin);
	//freopen("cannon.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){cin>>s;dfs(i,1,"",0);}
	if(n==1){//考虑只有一行的情况 
		for(int i=1;i<=g[1][0];i++){
			if(w[1][i]>tot) tot=w[1][i];
		}
		printf("%d\n",tot);
		return 0;
	}
	for(int i=1;i<=g[1][0];i++){
		for(int j=1;j<=g[2][0];j++){
			int k1=g[1][i],k2=g[2][j];
			int tem=k1&k2;
			if(tem!=0) continue;
			f[2][i][j]=w[1][i]+w[2][j];
			if(f[2][i][j]>tot) tot=f[2][i][j];
		}
	}
	DP();
	printf("%d\n",tot);
	return 0;
}
void DP(){
	for(int i=3;i<=n;i++){
		for(int k1=1;k1<=g[i-2][0];k1++){
			for(int k2=1;k2<=g[i-1][0];k2++){
			    int tem1=g[i-2][k1],tem2=g[i-1][k2];
				int tem=tem1&tem2;
				if(tem!=0)continue;
				tem=tem1|tem2;
				//cout<<fa[i-2][k1]<<' '<<fa[i-1][k2]<<endl;
				for(int k3=1;k3<=g[i][0];k3++){
					int tem3=g[i][k3];
				    int flag=tem3&tem;
				    if(flag!=0)continue;
				    if(f[i][k2][k3]<f[i-1][k1][k2]+w[i][k3])f[i][k2][k3]=f[i-1][k1][k2]+w[i][k3];
				}	
			}
		}
	}
	for(int i=1;i<=g[n-1][0];i++){
		for(int j=1;j<=g[n][0];j++){
			if(f[n][i][j]>tot) tot=f[n][i][j];
		}
	}
	return;
}
void dfs(int i,int j,string k,int t){
	if(j>m){
		g[i][0]++;
		int tem=g[i][0];
		//fa[i][tem]=k;
		g[i][tem]=zh(k);
		w[i][tem]=t;
		return;
	}
	if(s[j-1]=='P'){
		string tem=k+"100";
		if(tem.size()>m) tem=tem.substr(0,m);
		dfs(i,j+3,tem,t+1);
	}
	string tem=k+"0";
	if(tem.size()>m) tem=tem.substr(0,m);
	dfs(i,j+1,tem,t);
}

上一题下一题代码讨论统计