@hsxrr
2017-02-28T09:37:54.000000Z
字数 5642
阅读 973
DP
题意
求区间[n,m]中有多少个不含62和4的数字
思路
数位DP，dp[i位][首位数为k]有多少种数字
那么dp[i][k] = dp[i-1][所有满足条件的k]之和
在求[0,m]中的所有情况时候可以利用dp[i][0] = i位数以内的所有情况总和降低一部分时间复杂度
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int N = 1e6+7;
int dp[10][10];
void init(){
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
for(int i = 1 ; i < 10 ; i++)
for(int k = 0 ; k < 10 ; k++)
for(int j = 0 ; j < 10 ; j++)
if( j != 4 && ( j != 6 || k != 2 ) ) dp[i][j] += dp[i-1][k];
}
int find1(int x , bool limt , int we){
if( x < 0 ) return 0;
if( x == 0 ) return 1;
int ans = 0 , i , t = 1;
for( i = 1 ; x >= t ; i++ , t*=10);
ans += dp[--i][0];t /= 10;
for(int k = 1 ; k < 10 ; k++ ){
if( limt && k == 2 && i == we ) continue;
if( x >= (k+1) * t - 1 ) ans += dp[i][k];
else{
if( dp[i][k] == 0 ) return ans;
int need = x - k*t;
ans += find1(need,k == 6 ? true : false, i-1);
return ans;
}
}
return ans;
}
int main(){
init();
int n,m;
while( scanf("%d%d",&n,&m) != EOF && n && m )
printf("%d\n",find1(m,false,-1) - find1(n-1,false,-1));
return 0;
}
题意
一个圆盘上面有n小格，小格按1-n的顺序编号，这个时候转动转盘m次，每次转盘都会转动ai格，但是可能顺时针或者逆时针，概率相等，问最后停在[l,r]区间的概率是多少
思路
用DP[i][k]表示第i次转动的时候编号为k的概率，那么每一个DP[i][k]都会向两个DP[i+1][k->顺],DP[i+1][k->逆]转移，这时候这两个就加上DP[i][k]的一半即可
最后把区间所有值加起来就是答案
因为m数字过大，所以这里要用滚动数组
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int N = 207;
double dp[N][2];
int main(){
int n,m,l,r,w;
while( scanf("%d%d%d%d",&n,&m,&l,&r) != EOF && n ){
memset(dp,0.0,sizeof(dp));
dp[1][0] = 1.0;
for(int i = 1 ; i <= m ; i++){
scanf("%d",&w);
w %= n;
for(int k = 1 ; k <= n ; k++){
if( k - w < 1 ) dp[n - w + k][i&1] += dp[k][!(i&1)] * 0.5;
else dp[k-w][i&1] += dp[k][!(i&1)] * 0.5;
if( k + w > n ) dp[w + k - n][i&1] += dp[k][!(i&1)] * 0.5;
else dp[k+w][i&1] += dp[k][!(i&1)] * 0.5;
dp[k][!(i&1)] = 0.0;
}
}
double ans = 0.0;
for(int i = 1 ; i <= n ; i++) if( i >= l && i <= r ) ans += dp[i][m&1];
printf("%.4lf\n",ans);
}
return 0;
}
题意
有一排村庄，这些村庄都在一条直线上，且每个村庄都有自己的坐标，现在要在这些村庄里面建立一些邮局，使得每个村庄到最近的邮局的距离之和最小
求这个距离的最小值
思路
首先预处理一个数组使得其记录用一个邮局覆盖vis[村庄i,村庄k]的最小距离之和，这时用dp[村庄1到村庄i][k个邮局]下的最小距离
那么dp[i][k] = min(dp[i][k],dp[j从1-i-1][k-1] + vis[j+1,k])
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int N = 307;
const int M = 35;
const int INF = 0x3f3f3f3f;
int dp[N][M] , vis[N][N] , p[N];
int main(){
int v,q;
while( scanf("%d%d",&v,&q) != EOF ){
memset(vis,0,sizeof(vis));
for(int i = 1 ; i <= v ; i++) scanf("%d",p+i);sort(p+1,p+1+v);
for(int i = 1 ; i <= v ; i++)
for(int k = i+1 ; k <= v ; k++)
vis[i][k] = vis[i][k-1] + p[k] - p[(i+k)/2];
for(int i = 1 ; i <= v ; i++) dp[i][1] = vis[1][i] , dp[i][i] = 0;
for(int i = 2 ; i <= q ; i++)
for(int k = i+1 ; k <= v ; k++){
dp[k][i] = INF;
for(int j = i-1 ; j < k ; j++) dp[k][i] = min(dp[k][i],dp[j][i-1] + vis[j+1][k]);
}
printf("%d\n",dp[v][q]);
}
return 0;
}
题意
用1*2的砖块铺满h*w的地面的铺发有多少种，砖块不可分半，对称后相同或者旋转后相同算多种
思路
状态压缩DP
把每一行中的铺设情况定位一个w位的二进制数，1表示这个格铺了横砖或者竖砖，0表示上一行铺了竖砖
那么用一个path数组记录所有本行为状态path[i]下上一行的状态
这时用dfs暴力枚举一行中出现的所有情况
1. 对于第k格有铺设横砖，如果此处能够铺设横砖，那么上一行的状态必然是铺满状态，所有这一行的两格和上一行的两格均为1
2. 如果本格铺设竖砖，那么把上一格的状态置0，本格状态置1
3. 如果上一格铺设竖砖，那么把上一格的状态置1，本格状态置0以区分竖砖状态
而我们枚举了所有的本行和上一行的状态，那么每一个上一行都有可能能成为本行状态，所以状态转移的时候直接把所有上一行的情况，叠加到本行的情况即可，最后最后一行铺满的状态即为答案，注意初始化第0行铺满
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int N = 12;
const int M = 35;
const int INF = 0x3f3f3f3f;
typedef long long LL;
LL dp[N][1<<N];
int path[N*(1<<N)][2];
void dfs(int l , int now , int pre , int w , int& tan ){
if( l > w ) return;
if( l == w ){
path[tan][0] = pre;
path[tan++][1] = now;
return;
}
dfs(l+2,(now<<2)|3,(pre<<2)|3,w,tan);
dfs(l+1,(now<<1)|1,pre<<1,w,tan);
dfs(l+1,now<<1,(pre<<1)|1,w,tan);
}
int main(){
int h,w,tan;
while( scanf("%d%d",&h,&w) != EOF && h ){
if( w > h ){
int temp = w;
w = h;
h = temp;
}
if( w * h % 2 == 1){
printf("0\n");
continue;
}
memset(dp,0,sizeof(dp));
tan = 0;
dfs(0,0,0,w,tan);
dp[0][(1<<w)-1] = 1;
for(int i = 0 ; i < h ; i++){
for(int k = 0 ; k < tan ; k++){
dp[i+1][path[k][1]] += dp[i][path[k][0]];
}
}
printf("%lld\n",dp[h][(1<<w)-1]);
}
return 0;
}
题意
中文题
xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？
如果能升完这级求出还能保留的最大忍耐度
思路
二维动态规划问题dp[忍耐度][杀怪数],其中装最大获得经验
这是对于每一杀怪数都需要对每种怪进行便利，忍耐度作为最外层循环，一旦经验满足条件就结束循环，当前忍耐度为最小消耗忍耐度
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int N = 110;
const int M = 35;
const int INF = 0x3f3f3f3f;
int dp[N][N] , a[N] , b[N];
int main(){
int n,m,k,s,i,j,kill;
while( scanf("%d%d%d%d",&n,&m,&k,&s) != EOF ){
memset(dp,0,sizeof(dp));
for(i = 1 ; i <= k ; i++) scanf("%d%d",a+i,b+i);
for(i = 1 ; i <= m ; i++){
for(j = 1 ; j <= k ; j++){
for(kill = 1 ; kill <= s ; kill++){
int d = 1;
while( d * b[j] <= i && d <= kill ){
dp[i][kill] = max(dp[i][kill] , dp[i-d*b[j]][kill-d] + d * a[j]);
d++;
}
}
}
if( dp[i][s] >= n ) break;
}
if( i > m ) printf("-1\n");
else printf("%d\n",m-i);
}
return 0;
}
题意
有一个公司要开PARTY，但是有一个奇怪的规定，就是有直接上下司关系的人不能同时参加，每个人如果参加party就会为party增加一定的活跃值，现在问最大活跃值是多少
思路
用一个数来存储整个公司的上下司关系，这时候需要总每一个祖节点去找递归确认每个人去或者不去，假设dp[i,k]表示第i个人的状态是k，（k取值0，1分别表示不去和去两种状态），那么对于每个有下司的人都有状态转移方程dp[i,0] = 求和所有下司max(dp[下司,1],dp[下司,0]);dp[i,1] = 求和所有下司dp[下司,0] + 本人的活跃值;
如果没有下司那么dp[i,1] = 本人活跃值，dp[i,0] = 0;
这是最需要知道祖节点的max(dp[ans,0],dp[ans,1]);
测试数据中不含多个祖节点的情况
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int N = 6007;
const int M = 35;
const int INF = 0x3f3f3f3f;
struct node{
int fa;
vector<int> son;
int val;
void clear(int i,int v){
fa = i;
son.clear();
val = v;
}
}q[N];
bool falg[N] , vis[N];
int p[N],dp[N][2];
void dfs(int root){
if( vis[root] ) return;
dp[root][0] = 0;
dp[root][1] = q[root].val;
vis[root] = true;
for(auto it = q[root].son.begin() ; it != q[root].son.end() ; it++ ){
dfs(*it);
dp[root][0] += max(dp[*it][1],dp[*it][0]);
dp[root][1] += dp[*it][0];
}
}
int main(){
int n,a,b;
while( scanf("%d",&n) != EOF ){
for(int i = 1 ; i <= n ; i++) scanf("%d",p+i) , falg[i] = false, q[i].clear(i,p[i]) , vis[i] = false;
while( scanf("%d%d",&a,&b) != EOF && a ){
q[a].fa = b;
falg[a] = true;
q[b].son.push_back(a);
}
a = 1;
while( falg[a] ) a++;
memset(dp,0,sizeof(dp));
dfs(a);
printf("%d\n",max(dp[a][0],dp[a][1]));
}
return 0;
}