BZOJ 1079 着色方案(DP)
2024-09-03 14:43:15
如果把当前格子涂什么颜色当做转移的话,状态则是每个格子的颜色数还剩多少,以及上一步用了什么颜色,这样的状态量显然是5^15.不可取。
如果把当前格子涂颜色数还剩几个的颜色作为转移的话,状态则是每个格子的还剩多少个的颜色数,以及上一步用了还剩几个的颜色,这样的状态量为15^5.
那么定义dp[a][b][c][d][e][last].表示涂到当前格子时还剩1个的颜色数为a.......且上一步涂了还剩last个的颜色。
转移方程就很明显了.
/**************************************************************
Problem: 1079
User: freeloop
Language: C++
Result: Accepted
Time:52 ms
Memory:56588 kb
****************************************************************/ # include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... int vis[];
LL dp[][][][][][];
bool mark[][][][][][]; LL dfs(int a, int b, int c, int d, int e, int last)
{
if (mark[a][b][c][d][e][last]) return dp[a][b][c][d][e][last];
LL ans=;
if (a) ans+=dfs(a-,b,c,d,e,)*(last==?a-:a);
if (b) ans+=dfs(a+,b-,c,d,e,)*(last==?b-:b);
if (c) ans+=dfs(a,b+,c-,d,e,)*(last==?c-:c);
if (d) ans+=dfs(a,b,c+,d-,e,)*(last==?d-:d);
if (e) ans+=dfs(a,b,c,d+,e-,)*e;
mark[a][b][c][d][e][last]=;
return dp[a][b][c][d][e][last]=ans%MOD;
}
int main ()
{
int n, x;
scanf("%d",&n);
FOR(i,,n) scanf("%d",&x), ++vis[x];
FOR(i,,) dp[][][][][][i]=, mark[][][][][][i]=;
dfs(vis[],vis[],vis[],vis[],vis[],);
printf("%lld\n",dp[vis[]][vis[]][vis[]][vis[]][vis[]][]);
return ;
}
最新文章
- 使用winmm.dll 获取麦克风声音数据
- Netty(三)TCP粘包拆包处理
- strncpy,strcpy
- [AHOI 2009] 维护序列(线段树模板题)
- 二模12day2解题报告
- echart.js的使用与API
- handler以及AnyscTask处理机制
- Idea实现WebService实例 转
- Android 首次进入应用时加载引导界面
- 引用 U-boot给kernel传参数和kernel读取参数—struct tag
- sql的存储过程使用详解--基本语法
- ubuntu 装机步骤表
- 002_运维SOP
- [转] Linux有问必答:如何修复“sshd error: could not load host key”
- 【BZOJ】3572: [Hnoi2014]世界树
- 78. Subsets C++回溯法
- Android点击事件
- python之旅:文件处理
- JS验证表单中TEXT文本框中是否含有非法字符
- ExtJS 6.2 基础使用