「JoyOI1469」飘飘乎数独
背景 Background
为了能够赶在Candy生日这天送给她一个特制的礼物，飘飘乎居士最近一直躲在家中研究自己发明的飘飘乎数独
描述 Description
飘飘乎数独每行的数字都由1~m自然数填满（每行中每个数字用且只能用一次），但相邻的自然数（5 4与4 5都认为相邻）却不会出现在相邻的方格中（包括左右相邻和上下相邻），对于这样的一个飘飘乎数独，当然有许许多多的填法。但是，飘飘乎数独每一列都有一个得分规则：第i列的得分为第i列所有自然数的总和*i，最后的总分即为m列得分之和。飘飘乎居士当然希望给Candy的礼物是一个总分最大的飘飘乎数独
输入格式 InputFormat
第一行，两个正整数n m，表示一个n*m飘飘乎数独
接下来一个矩阵，矩阵的每一行数为一个非负数，0表示飘飘乎居士需要用1~m其中一个自然数填充的方格，非0自然数代表已经填充过的方格（即不能够更改的方格）
输出格式 OutputFormat
一行，最后的总分
数据范围和注释 Hint
最优的飘飘乎数独为(并且只存在这一种方案)
1 3 5 2 4
4 1 3 5 2
规定横竖都不能有相邻的自然数，但可以有相等的自然数
得分为第一列 1*(1+4)=5
第二列 2*（3+1）=8
第三列 3*（5+3）=24
第四列 4*（2+5）=28
第五列 5*（4+2）=30
总分为95，也就是最后的答案
对于30%的数据， 保证 3<=n m<=5，0的个数<=10个
对于100%的数据，保证 3<=n m<=7 0的个数<=n*m
数据保证至少存在一个解。
题解
暴力三十分非常高兴
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<iostream> #include<cstdio> #define searchnext(x,y) y==m? search(x+1,1):search(x,y+1) using namespace std; int n,m,ans; int a[8][8],b[8][8],used[8][8]; int getans(int t[8][8]) { int s=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) s+=(t[j][i]*i); return s; } bool jud(int x,int y){if((x-y==1||y-x==1)&&(x*y!=0))return 0;return 1;} bool judge(int x,int y,int k) { if(used[x][k])return 0; if(x>1&&!jud(a[x-1][y],k))return 0; if(x<n&&!jud(a[x+1][y],k))return 0; if(y>1&&!jud(a[x][y-1],k))return 0; if(y<m&&!jud(a[x][y+1],k))return 0; return 1; } void search(int x,int y) { if(x==n+1){ans=max(ans,getans(b));return;} if(a[x][y]){b[x][y]=a[x][y];searchnext(x,y);} else { for(int i=1;i<=m;i++) { if(judge(x,y,i)) { b[x][y]=i;used[x][i]=1; searchnext(x,y); b[x][y]=0;used[x][i]=0; } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int x;scanf("%d",&x); a[i][j]=x; used[i][x]=1; } search(1,1); printf("%d",ans); return 0; } |
加个剪枝90分。。
f[i]表示不考虑冲突从第i行开始后的所有行能获得的最大分值
如果搜到第i行得分s，且s+f[i]<=ans，就return
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<iostream> #include<cstring> #include<cstdio> #define searchnext(x,y,s) y==m? search(x+1,1,s):search(x,y+1,s) using namespace std; int n,m,ans; int a[10][10],used[10][10],f[10]; bool jud(int x,int y){if((x-y==1||y-x==1)&&x!=0)return 0;return 1;} bool judge(int x,int y,int k) { if(used[x][k])return 0; if(x>1&&!jud(a[x-1][y],k))return 0; if(x<n&&!jud(a[x+1][y],k))return 0; if(y>1&&!jud(a[x][y-1],k))return 0; if(y<m&&!jud(a[x][y+1],k))return 0; return 1; } void search(int x,int y,int s) { if(x==n+1){ans=max(ans,s);return;} if(y==1&&s+f[x]<=ans)return; if(a[x][y]){searchnext(x,y,s+a[x][y]*y);return;} for(int i=1;i<=m;i++) { if(judge(x,y,i)) { a[x][y]=i;used[x][i]=1; searchnext(x,y,s+i*y); a[x][y]=0;used[x][i]=0; } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&a[i][j]); used[i][a[i][j]]=1; } bool t[10]; for(int i=n;i>0;i--) { f[i]=f[i+1];memset(t,0,sizeof(t)); for(int j=m,k=m;j>0;j--) if(a[i][j])f[i]+=a[i][j]*j; else { for(;k>0;k--) if(!t[k]&&!used[i][k]){f[i]+=k*j;t[k]=1;break;} } } search(1,1,0); printf("%d",ans); return 0; } |
正解状压以后写
Subscribe
计数器 9856115
OI 课件=>
OI 课件=>