365bet体育可能是 · 最无尊重之freestyle教学。DP大作战—状态压缩dp

乱,睡意全无,夜不能寐,孤枕难眠,翻来覆去

题材叙述

阿姆斯特朗回旋加速式阿姆斯特朗炮是千篇一律种植好厉害的器械,这种武器可以摧毁自己同行和排两个单位范围外之保有其他单位(其实就算是十字型),听起来比较红警里面的法国巨炮可是厉害多了。现在,零崎要于地形图及摆一切开阿姆斯特朗回旋加速式阿姆斯特朗炮,那么在N行M列单位长度大小的地图及,求解阿姆斯特朗回旋加速式阿姆斯特朗炮最深的布数量以及相应部署方案总数。

追思今天freestyle输给了同班的小明,你眉头一皱叹了人数暴,手里的被捏得重复不方便了

输入

每组输入一行,为有限只整数N,M (N <= 100;M <= 10)

“怎么连free个style都不如人家?”

输出

每组一行简单独整数,

率先只为阿姆斯特朗回旋加速式阿姆斯特朗炮的个数,第二单呢夫数额下之摆设方式总数。

重复看看别人家的孩子:

输入样例

3 3

优先变更着急在闷气,

出口样例

3 6

自看你骨骼清奇、根骨极美好,必是百年一遇的嘻哈奇才!我这边产生本freestyle真传绝学,今日与汝有缘,就半货半送了过!

Hint

100   1为阿姆斯特朗回旋加速式阿姆斯特朗炮的位置,方案不唯一。  
010
001

状态压缩是同一栽奇特之技巧,不止可以为此当dp中。状态压缩其实是在以数据结构,由于底子数据类型int有32个,一个int变量就得代表2^32个状态。状态压缩其实是千篇一律种优化措施,有大挺局限性。第一,单元状态一般仅来三三两两栽(0、1,其实多了削减的理是同一的,但是没有个运算就从未什么优势了),第二,单元维度通常不跳50
( int才32,多矣longlong都爆掉难道用大精度大整数压缩不化……)

状压dp本质上要dp,问题大多数还是求解最可怜价值或者解决方案总数之类的,但是状态数量巨大普通方法难以表示,所以利用整数可以拿状态维度压缩至1维。

题材来:http://biancheng.love/contest/10/problem/G/index

解题思路:

状态压缩dp问题。

关于状态压缩问题参见:http://www.cnblogs.com/avril/p/3282295.html

其他状态压缩DP问题:【POJ3254】【POJ1185】【POJ3311】【HDU3001】【POJ2288】【ZOJ4257】【POJ2411】【HDU3681】

吃起主题代码:

 1 #include <bits/stdc++.h>
 2 #define INF 99999999
 3 typedef long long LL;
 4 using namespace std;
 5 
 6 const int MAX=100+10;
 7 int n,m,lastsize,lastlastsize,nowsize;
 8 int last[MAX],lastlast[MAX],now[MAX];
 9 int num[MAX],dp[MAX][MAX],temp[MAX][MAX];//dp[k][i][j]表示第k行选择i方案,第k-1行选择j方案的最大炮兵数
10 
11 void dfs(int id,int k,int p,int sum)
12 {
13     if(k>=m)
14     {
15         now[++nowsize]=p;
16         num[nowsize]=sum;
17         return;
18     }
19     dfs(id,k+3,p|(1<<k),sum+1);
20     dfs(id,k+1,p,sum);
21 }
22 
23 void DP()
24 {
25     for(int k=1; k<=n; ++k)
26     {
27         memset(now,0,sizeof now);
28         nowsize=0;
29         dfs(k,0,0,0);
30         for(int i=1; i<=nowsize; ++i)for(int j=1; j<=lastsize; ++j)dp[i][j]=0;
31         for(int i=1; i<=nowsize; ++i) //本行选择第几个方案
32         {
33             for(int j=1; j<=lastsize; ++j) //上一行选择第几个方案
34             {
35                 for(int t=1; t<=lastlastsize; ++t) //上上行选择第几个方案
36                 {
37                     if(now[i] & last[j])continue;//与上一行j方案不能共存
38                     if(now[i] & lastlast[t])continue;//与上上行t方案不能共存
39                     if(dp[i][j]<temp[j][t]+num[i])dp[i][j]=temp[j][t]+num[i];
40                 }
41             }
42         }
43         for(int i=1; i<=nowsize; ++i)for(int j=1; j<=lastsize; ++j)temp[i][j]=dp[i][j];
44         for(int i=1; i<=lastsize; ++i)lastlast[i]=last[i];
45         lastlastsize=lastsize;
46         for(int i=1; i<=nowsize; ++i)last[i]=now[i];
47         lastsize=nowsize;
48     }
49 }
50 
51 int main()
52 {
53     while(~scanf("%d%d",&n,&m))
54     {
55         last[1]=lastlast[1]=temp[1][1]=0;
56         lastsize=lastlastsize=1;
57         DP();
58         int sum=0,cot;
59         for(int i=1; i<=lastsize; ++i)
60         {
61             for(int j=1; j<=lastlastsize; ++j)
62             {
63                 if(temp[i][j]>sum)
64                 {
65                     sum=temp[i][j];
66                     cot=1;
67                 }
68                 else if(temp[i][j]==sum)
69                     cot++;
70             }
71         }
72         printf("%d %d\n",sum,cot);
73     }
74     return 0;
75 }

 

卿莫待知道啊是flow, bridge, hook

公只待一个熊熊燃烧的freestyle魂

相对而言,Papi酱的示范只能称得达雕虫小技巧不足挂齿,赶紧搬个小板凳拿上瓜,听我一一道来

阿姆斯特朗回旋连押

立是种植听似变化万总而规律简单的freestyle必杀技,把简单的几乎独字组合循环,你不怕来了极端有穿透力的词:

公猜猜我怀疑你怀疑我猜测你猜我猜你猜猜我猜想你怀疑我猜测你猜不蒙

我猜你猜我猜测你猜猜我怀疑你怀疑我猜测你猜我猜你猜猜我猜想你怀疑不至

为有句内押韵和转乾坤特点,歌词复杂的逻辑给对手难以从中找到破绽,由此江湖得叫阿姆斯特朗回旋连押

出口就只见 —— 人飞檐走壁,天斗转星移

除去“我猜测你猜猜”的句式,“我说你说” “我清楚您懂得”之类的句式也为人津津乐道

跳蛋夺命九押真经

顾名思义,这记杀手锏能在句尾形成9
次押韵,就像跳蛋一样挑拨着对方每根神经。
在出啊哈节目遭到,选手们经常会面利用单押/双押的技能,但是在九押前边,它们只能跪下来喊爸爸:

自押韵真绝狠心了了了了了了了了了

君没法和自己比较之底底的的的的之之

在同淫秽又同样淫秽的押韵之下,你的freestyle被推动了高潮,对手的思防线就崩溃,他内心清楚,只要同开口,自己便输了

古代的绝密力量

随即是均等套传自古人的押解韵大法,欲练此功,必先闭门苦读,饱览四书五经,熟读唐诗宋词,才会编得正果:

床铺前方明月光,疑是地上霜,举头为明月,低头思故乡!

刚刚所出示的,是此法的绝低档境界;随着文化之累与语速的增速,你的地步会愈加强,只要熟练此法,即可成为芸芸众生中之一致湾清流,让听众们忍不住地点头跟着唱起

排山倒海式双押

是也殊轻学会,如想被好之 freestyle
拥有推开高山、翻倒大海的威力,你只有待扯高嗓门,再增长以下动作:

斯招能让freestyle的气焰和力量变得空前繁荣,话音刚落便用对准手击倒在地

(纯属娱乐,模仿用谨慎)

相此间,恭喜您

出师了

报了若这样多,该轮到公来发泄一手了咔嚓?

尚眷恋看还多的 freestyle 绝招嘛?

怀念了解其他人的嘻哈风采嘛?

今日快来和 点击这里
和大伙 freestyle 吧

乃既然可唱来好之freestyle,还会十分别人的啊!如果你认为挺,还可以以他的状态下与外battle!

举手投足网站 by 早睡飞船

贴张网站的配图:

相关文章