私信TA

用户名:uq_42410893353

访问量:3078

签 名:

菜狗只希望蓝桥杯拿个好成绩,呜呜~

等  级
排  名 4409
经  验 1615
参赛次数 0
文章发表 21
年  龄 0
在职情况 学生
学  校 韩庄乡男子电力职业技术学院
专  业

  自我简介:

数位DP,动态规划(DP)的一种,在本题中表示为使用二进制表示糖果情况,第i位上为0代表第i种糖果不能吃到,为1则代表能吃到。

用a[n]表示在二进制数为n时需要的最少糖果袋数,f[n]表示初始的n个糖果袋的二进制数,定义maxn等于最终的二进制数。

状态转移方程:a[j|f[i]]=min(a[j|f[i]],a[j]+1)
(我用了一个转化为二进制数输出的函数e,可以自己定义一个输出一下,会让本题更加直观)
参考代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
const int N=1<<20;
int n,m,k,a[N],f[110];
void e(int x){
	for(int i=0;i<20;i++){
		cout<<x%2;
		x/=2;
	}
	cout<<endl;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    int maxn=(1<<m)-1;
    //e(maxn);
    for(int i=0;i<=maxn;i++)a[i]=200;
    for(int i=0;i<n;i++){
    	int x;
    	for(int j=0;j<k;j++){
    		scanf("%d",&x);
    		f[i]|=1<<(x-1);
		}
		a[f[i]]=1;
		//e(f[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=1;j<=maxn;j++){
			if(a[j]!=200){
				a[j|f[i]]=min(a[j|f[i]],a[j]+1);
				//e(j);
				//e(j|f[i]);
			}
		}
	}
	if(a[maxn]==200)cout<<-1;
	else cout<<a[maxn];
}


 

0.0分

5 人评分

  评论区