首页 > ACM题库 > HDU-杭电 > HDU 2858-Oil on the Mars-动态规划-[解题报告]HOJ
2014
02-17

HDU 2858-Oil on the Mars-动态规划-[解题报告]HOJ

Oil on the Mars

问题描述 :

According to top-secret mars sensor transition, a big oil field was founded on the Mars. The field is divided into N*M equal square, and each square contains some oil resources. Our army want to occupy all the territory of the field, but the UN (United Nations) will allow us to occupy only K squares. Of course, we want to get control over as many oil as possible, but, we will have to guard all our territory. So, they need our territory to be easy-controlled, i.e. from any square to any it must be possible to get moving only along two directions (selected from the next list: left, right, up, down; for different squares pairs of directions may differ).
You are to write a program, which determines, how many oil will be occupied by us.

输入:

There are several test cases. On the first line of input there are 3 integer numbers N,M,K (1<=N,M<=15, 0<=K<=N*M). The next N lines contain M integers each, which are the number of oil resource on that square. Each of this numbers lies in range of 0 to 1000.

输出:

There are several test cases. On the first line of input there are 3 integer numbers N,M,K (1<=N,M<=15, 0<=K<=N*M). The next N lines contain M integers each, which are the number of oil resource on that square. Each of this numbers lies in range of 0 to 1000.

样例输入:

2 3 4 
10 20 30 
40 2 3

样例输出:

Oil : 100 

       题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2858

     这个题目意思开始一直没理解清楚,后来看了一个大牛的代码才理解到,其实就是选一个有k个方格的区域,区域的轮廓线没有凹陷,我们可以一行一行的处理,易知每行必须是连续区域(不然会出现凹陷),然后用dp[k][l][j][nl][nr][level][row]记录最后一行的行号为row,还要选k个方格,最后一行选的是区域(i,j),且后续决策允许的的区域在[nl,nr]之间能得到的最大价值。但是这个题卡内存,直接dp不行,只有用bfs搜索,去掉无用状态。

#include<iostream>
#include<queue>
#include<string.h>
#include<stdio.h>
using namespace std;
struct node
{
    int k,l,r,ans,nl,nr,level;
    node(){};
    node(int kk,int ll,int rr,int anss,int nll,int nrr,int le)
    {
        k=kk;l=ll;r=rr;ans=anss;level=le;nl=nll;nr=nrr;
    }
    friend bool operator<(const node &A,const node &B)
    {
        if(A.level==B.level)
        {
            return A.ans<B.ans;
        }
        return A.level>B.level;
    }

}s,e;
bool hash[230][15][15][15][15][2];
priority_queue<node>q;
int map[20][20],b[20][20][20];
int n,m,k,ans;
int x,y,now;
void solve()
{
	if(e.k<0||e.k>(n-e.level-1)*(e.nr-e.nl+1))
		return;
	if(hash[e.k][e.l][e.r][e.nl][e.nr][1-now]==true)
		return;
	q.push(e);
	hash[e.k][e.l][e.r][e.nl][e.nr][1-now]=true;
}
void bfs(int l)
{
	int i,j;
	memset(hash,0,sizeof(hash));
	q.push(node(0,0,0,0,0,0,-1));
	while(!q.empty())
	{
		s=q.top();
		q.pop();
		if(s.k==0&&s.ans>ans)
			ans=s.ans;
        if(s.level==n-1)
            continue;
		if(s.level!=l)
		{
			now=1-now;
			l=s.level;
            for(i=0;i<m;i++)
            {
                for(j=i;j<m;j++)
                {
                    e=s;
                    e.level++;
                    e.l=i;
                    e.r=j;
                    e.nl=0;
                    e.nr=m-1;
                    e.k=k-(j-i+1);
                    e.ans=b[e.level][i][j];
                    solve();
                }
            }
		}
		hash[s.k][s.l][s.r][s.nl][s.nr][now]=false;
        if(s.level==-1)
            continue;
		if(s.k>(n-s.level-1)*(s.nr-s.nl+1))
			continue;
		for(i=s.nl;i<=s.nr;i++)
		{
			for(j=i;j<=s.nr;j++)
			{
				//printf("ans%d\n",e.ans);
				if(i<s.nl||j>s.nr||j<s.l||i>s.r)
					continue;
				e=s;
				e.level++;
				e.l=i;
				e.r=j;
				e.k-=(j-i+1);
				if(i>s.l&&j<s.r)
				{
					e.nl=i;
					e.nr=j;
					e.ans+=b[e.level][i][j];
				}
				else if(i>s.l)
				{
					e.nl=i;
					e.nr=s.nr;
					e.ans+=b[e.level][i][j];
				}
				else if(j<s.r)
				{
					e.nl=s.nl;
					e.nr=j;
					e.ans+=b[e.level][i][j];
				}
				else
				{
					e.nl=s.nl;
					e.nr=s.nr;
					e.ans+=b[e.level][i][j];

				}
				solve();
			}
		}
	}
}
int main()
{
	int i,j;
	while(scanf("%d%d%d",&n,&m,&k)==3)
	{
		ans=0;
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			{
				scanf("%d",&map[i][j]);
				ans+=map[i][j];
			}
		}
		for(i=0;i<n;i++)
		{
			for(x=0;x<m;x++)
			{
				for(y=x;y<m;y++)
				{
					if(y==x)
						b[i][x][y]=map[i][x];
					else
						b[i][x][y]=b[i][x][y-1]+map[i][y];
				}
			}
		}
		ans=0;
		now=0;
		bfs(-2);
		printf("Oil : %d\n",ans);
	}
	return 0;
}


解题参考:http://blog.csdn.net/wings_of_liberty/article/details/7358737


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  3. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮