果真看到题要先动脑子啊><这一题开始以为是DP,结果每一格状态和周围四格都有关系,卡在了状态转移><
最后发现,随手画一画就发现间隔着种树最优,因为保证了每一个fertilized point都有apple tree
不管是odd*even 还是 odd*odd的map,左上角种树一定是最优的(树最多),其他case两种左上角放不放树都一样。
然后直接遍历每个fertilized point,把周围的点*2,大神的解法没看懂><点击打开链接
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> #include<map> #include<time.h> using namespace std; //hdu 4925 int T; int N; int M; int mp[110][110]; int dx[]={0,-1,0,1}; int dy[]={-1,0,1,0}; int main() { freopen("input.txt","r",stdin); // freopen("data.txt","r",stdin); // freopen("out1.txt","w",stdout); scanf("%d",&T); while(T--) { scanf("%d %d",&N,&M); memset(mp,0,sizeof(mp)); for(int i=1;i<=N;i++) { for(int j=(i&1);j<=M;j=j+2) { mp[i][j]=1;//plant a tree } } for(int i=1;i<=N;i++) { for(int j=1+(i&1);j<=M;j+=2)//point that is fertlized { for(int k=0;k<4;k++) { int x=i+dx[k]; int y=j+dy[k]; if(x>=1&&x<=N&&y>=1&&y<=M) { mp[x][y]*=2; } } } } int ans=0; for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { ans+=mp[i][j]; } } printf("%d\n",ans); } return 0; }