锐客网

  1. 首页 > 生活百科 > it技术 > >

CF750D|CF750D New Year and Fireworks

传送门
暴力+搜索 手动打表它不香吗【逃~~ 首先想到用dfs来遍历烟花分支，用一张表来标记是否经过点，烟花一共有8个方向，而且很容易想到每一个方向过后都只有两个固定的方向可以选择，因此本题可以列举8个方向之后的2种可能来解决。
【CF750D|CF750D New Year and Fireworks】烟花可能会向四面八方绽开，如果原点为[0,0]，坐标可能会有负数，因此我们需要每次在表上操作时对坐标加一个偏移值。因为n<=30,ti<=5,所以最多向一个方向移动150个单位，偏移值为150，标记表开为300*300
需要注意的是，可能有同时在同一位置，同一方向的分支产生，这时需要记忆化，否则会超时QAQ
code:

#include using namespace std; const int M=150; int n,a[35],Map[305][305],ans,f[35][305][305][3][3]; void dfs(int step,int x,int y,int p,int q){//当前是第step层，开始坐标为[x,y] //x轴方向为p，y轴方向为q(用-1，1，0表示，x轴和y轴方向是数组存储顺序) if(f[step][x][y][p+1][q+1]) return; f[step][x][y][p+1][q+1]=1; //记忆化剪枝 if(step>n) return; //层数到n+1退出 int len=a[step]; //每次走的长度 for(int i=1; i<=len; i++){ x+=p; y+=q; //坐标更新 Map[x][y]=1; //每一步都标记 } int xx,yy; //表示下一步的方向 if(p==-1&&q==0) xx=-1,yy=-1; else if(p==-1&&q==-1) xx=0,yy=-1; else if(p==0&&q==-1) xx=1,yy=-1; else if(p==1&&q==-1) xx=1,yy=0; else if(p==1&&q==0) xx=1,yy=1; else if(p==1&&q==1) xx=0,yy=1; else if(p==0&&q==1) xx=-1,yy=1; else if(p==-1&&q==1) xx=-1,yy=0; dfs(step+1,x,y,xx,yy); //分支1if(p==-1&&q==0) xx=-1,yy=1; else if(p==-1&&q==1) xx=0,yy=1; else if(p==0&&q==1) xx=1,yy=1; else if(p==1&&q==1) xx=1,yy=0; else if(p==1&&q==0) xx=1,yy=-1; else if(p==1&&q==-1) xx=0,yy=-1; else if(p==0&&q==-1) xx=-1,yy=-1; else if(p==-1&&q==-1) xx=-1,yy=0; dfs(step+1,x,y,xx,yy); //分支2 } int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); dfs(1,M,M,-1,0); //注意起始坐标为[M,M] for(int i=0; i<=300; i++) for(int j=0; j<=300; j++) ans+=Map[i][j]; //遍历标记表 printf("%d",ans); return 0; }


    推荐阅读


    上一篇：@strongify(self)解析

    下一篇：Ubuntu上的oh-my-zsh