【蓝桥】dp

dp蓝桥练习

• • 邮票
  • 拿金币
  • 印章

给定一个信封，有N（1≤N≤100）个位置可以贴邮票，每个位置只能贴一张邮票。我们现在有M(M<=100)种不同邮资的邮票，面值为X1,X2….Xm分（Xi是整数，1≤Xi≤255），每种都有N张。

显然，信封上能贴的邮资最小值是min(X1, X2, …, Xm)，最大值是 N*max(X1, X2, …,  Xm)。由所有贴法得到的邮资值可形成一个集合（集合中没有重复数值），要求求出这个集合中是否存在从1到某个值的连续邮资序列，输出这个序列的最大值。

例如，N=4，M=2，面值分别为4分，1分，于是形成1，2，3，4，5，6，7，8，9，10，12，13，16的序列，而从1开始的连续邮资序列为1，2，3，4，5，6，7，8，9，10，所以连续邮资序列的最大值为10分。

#include 
#include 
using namespace std;
const int N=1e5+1;
int f[N]={0};
int main()
{
	int m,n;
	cin>>m>>n;
	int v[n];
	for(int i=0;i>v[i];
	}
	int j=0;
	while(f[j]<=m){
		j++;
		int m=1e5;
		for(int i=0;i 
拿金币 
#include 
using namespace std;
int n;
//全设置为0
int a[1002][1002] = {0};
int main(){
	int i,j;
	cin>>n;
    //从a[1][1]开始储存
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			cin>>a[i][j];
		}	
	}
	//动态规划，使得数组中每个值存放到达此点的所捡到的最大金币 
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
            //遍历数组，比较此数上方的值 和 此数左边的值，再用此数加上更大的值
			if(a[i-1][j] >= a[i][j-1]){
				a[i][j] += a[i-1][j];
			}else{
				a[i][j] += a[i][j-1];
			}
		}	
	}
    //右下角的值即为到达右下角所捡到的金币最大数
	cout << a[n][n];
	return 0;
} 

 
印章 
共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概
 
#include
using namespace std;
double dp[25][25],p;
int main()
{
	int n,m;
	cin >> n >> m;
	p=1.0/n;
//	 for(int i=0;i<21;i++){
//	 	a[1][i]=1;
//	 }
	 for(int i=1;i<=m;++i){
	 	for(int j=1;j<=n;++j){
	 		if(i 
dp根据是否重复分两种情况