网站开发合同适用印花税,wordpress自定义文章类型模板,网站使用支付接口如何收费,营销型网站建设主要教学内容剑之修炼
jzoj 2130
题目大意#xff1a;
在一个位置上有一个人#xff0c;同时还有NNN#xff08;N⩽10N \leqslant 10N⩽10#xff09;个怪物#xff0c;这个人会不停地释放技能#xff0c;技能可以瞬间杀死周围8个格子上的怪物#xff0c;行走速度是每个单位时间走…剑之修炼
jzoj 2130
题目大意
在一个位置上有一个人同时还有NNNN⩽10N \leqslant 10N⩽10个怪物这个人会不停地释放技能技能可以瞬间杀死周围8个格子上的怪物行走速度是每个单位时间走一个单位距离现在问这个人最快要多久才能杀死所有怪物还要输出路径
输入
输入是先输入地图范围S和怪兽数量N然后输入此人位置接下来n行每行表示怪兽的位置
输入样例#1 5 32 21 13 31 2输出样例#1
0输入样例#2
5 3
3 3
1 1
5 5
1 5输出样例#2
6
3 2
2 2
2 3
2 4
3 4
4 4数据范围
5⩽S⩽305 \leqslant S \leqslant 305⩽S⩽30 N⩽10N \leqslant 10N⩽10
解题思路
用状压DP压缩杀怪状态然后设f[s][i][j]f[s][i][j]f[s][i][j]为杀怪状态为s且现在在iii怪的j方向上j方向上j方向上然后每一次枚举从哪个位置到那个位置然后路径只要在DP的时候记录一下即可
代码
#includecstdio
#includecstring
#includeiostream
#define abs(x) (x)0?-(x):(x)
using namespace std;
int n,m,ans,sum,x[20],y[20],f[(112)][20][10],s[(112)][20][10],s1[(112)][20][10];
const int dx[9]{0,1,1,1,0,-1,-1,-1,0};
const int dy[9]{1,1,0,-1,-1,-1,0,1,0};
int dis(int from,int fw,int to,int tw)//计算两个点的距离
{int x1,x2,y1,y2;x1x[from]dx[fw];y1y[from]dy[fw];x2x[to]dx[tw];y2y[to]dy[tw];if ((abs(x1-x2))(abs(y1-y2))0){x11;}return (abs(x1-x2))(abs(y1-y2));
}
void dg(int S,int dep,int w)
{if (S1) return;int x1,x2,y1,y2,xx,yy;dg(S-(1dep),s[S][dep][w],s1[S][dep][w]);//递归下去x1x[s[S][dep][w]]dx[s1[S][dep][w]];//两个点的坐标from和toy1y[s[S][dep][w]]dy[s1[S][dep][w]];x2x[dep]dx[w];y2y[dep]dy[w];if (x1x2) xx1;//预处理else xx-1;if (y1y2) yy1;else yy-1;while (x1!x2)//往x2走{x1xx;printf(\n%d %d,x1,y1);}while (y1!y2){y1yy;printf(\n%d %d,x1,y1);}
}
int main()
{memset(f,127/3,sizeof(f)); scanf(%d %d %d %d,m,n,x[0],y[0]);f[1][0][8]0;for (int i1;in;i)scanf(%d %d,x[i],y[i]);for (int i1;i(1n1)-1;i)//枚举状态for (int to1;ton;to)//枚举到的点if (i(1to))//存在for (int from0;fromn;from)//从哪里来if ((i(1from)||from0)from!to)//存在且不相同for (int tw0;tw8;tw)//在to的那个方向if (x[to]dx[tw]0x[to]dx[tw]my[to]dy[tw]0y[to]dy[tw]m)//没出界for (int fw0;fw8;fw)//在from的那个方向if (x[from]dx[fw]0x[from]dx[fw]my[from]dy[fw]0y[from]dy[fw]m)//没出界if (f[i-(1to)][from][fw]dis(from,fw,to,tw)f[i][to][tw])//更优{f[i][to][tw]f[i-(1to)][from][fw]dis(from,fw,to,tw);//更新s[i][to][tw]from;//记录路径s1[i][to][tw]fw;}int k(1n1)-1;for (int i1;in;i)for (int j0;j9;j)if (f[k][ans][sum]f[k][i][j])//取最大ansi,sumj;printf(%d,f[k][ans][sum]);if (f[k][ans][sum]) dg(k,ans,sum);//递归输出return 0;
}
