本文共 1598 字，大约阅读时间需要 5 分钟。
思路：这是一道坑爹的动态规划，思路很容易想到，就是细节。
用dp[t][i][j]，表示在第t时间，锤子停在(i,j)位置能获得的最大数量。那么只要找到一个点转移到（i,j）收益最大即可。
#include#include #include #include #include #include #include #include #include #include #include #define pb push_back#define mp make_pair#define Maxn 2000010#define Maxm 80002#define LL __int64#define Abs(x) ((x)>0?(x):(-x))#define lson(x) (x<<1)#define rson(x) (x<<1|1)#define inf 100000#define lowbit(x) (x&(-x))#define Mod 1000000007using namespace std;int dp[13][100][100],g[13][100][100];int get_num(int t,int x1,int y1,int x2,int y2){ int i,j; if(x1>x2){ swap(x1,x2); swap(y1,y2); } int l,r,sum=0; if(x1==x2){ l=min(y1,y2); r=max(y1,y2); for(i=l;i<=r;i++){ sum+=g[t][x1][i]; } return sum; } if(y1==y2){ l=min(x1,x2); r=max(x1,x2); for(i=l;i<=r;i++){ sum+=g[t][i][y1]; } return sum; } for(i=x1;i<=x2;i++){ if((i-x1)*(y2-y1)%(x2-x1)==0){ sum+=g[t][i][(i-x1)*(y2-y1)/(x2-x1)+y1]; } } return sum;}int main(){ int n,d,m,t,i,j,x,y,z,k,T; while(scanf("%d%d%d",&n,&d,&m)!=EOF,n||m||d){ memset(dp,0,sizeof(dp)); memset(g,0,sizeof(g)); T=0; int ans=0; for(i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); g[z][x+d+1][y+d+1]=1; T=max(T,z); } n+=2*d+2; for(t=1;t<=T;t++){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ for(x=i-d;x<=i+d;x++){ for(y=j-d;y<=j+d;y++){ if(x<=0||x>n||y<=0||y>n) continue; if((x-i)*(x-i)+(y-j)*(y-j)<=d*d){ dp[t][i][j]=max(dp[t][i][j],dp[t-1][x][y]+get_num(t,i,j,x,y)); ans=max(ans,dp[t][i][j]); } } } } } } printf("%d\n",ans); } return 0;}
转载于:https://www.cnblogs.com/wangfang20/p/3300831.html