hdu 5110 Alexandra and COS
虽然可以一眼看出是dp相关的,但题目给的数据量范围还是很容易把人吓住。题解的方法看来真是可行的。。。
根据题意,所要统计的点在正北方向左右45°的扇区内。设dp[i][j][k]表示观察点坐标为i,j,值为k。
若k <= sqrt(n)
dp[i][j][k] = dp[i-k][j-k][k] + dp[i-k][j+k][k] - dp[i-2*k][j][k] + 第i行区间[j-k,j+k]内的点数
该公式只表明大概的递推方向,一些边边角角的情况(如i<k, i<2*k, j<k, j+k>m等)仍需酌情处理
k > sqrt(n)
暴力解决
#include<cstdio>
#include&......
阅读全文