CF750D|CF750D New Year and Fireworks CF750DNewYearandFireworks

传送门
暴力+搜索 ~~手动打表它不香吗~~【逃~~ 首先想到用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; }

CF750D|CF750D New Year and Fireworks

推荐阅读

同类色对比照片摄影同类色

珂的意思和含义

聊城有哪些县聊城都有哪些区县

为什么像汉字一样的象形文字很少,多数语言是拼音文字呢？

button的超级链接

支付宝商户如何开通花呗收款？花呗收钱开通的方法

画新娘妆和盘头多少钱，画一个新娘妆大概多少钱

坐飞机可以戴隐形眼镜吗？

茯苓绿豆粥——清热祛湿利尿消肿

嘉宝果泡酒多久可以喝

星巴克全职星级咖啡师面试难吗？

建筑软件,我的世界导入建筑软件

听书安卓1.5,喜马拉雅蜻蜓fm懒人听书不错!

医保卡余额怎么用医保卡余额使用技巧

iOS|iOS 碰撞角度矫正及 applyImpulse 和 applyForce的区别

唇色发紫日常养护嘴唇发黑是什么原因

为什么梦见打雪仗

榴莲一半硬一半软是什么原因

顾炀樊渊是哪部小说

梦见理发你知道预示着什么吗