牛客网算法竞赛入门课练习题单6+其他dp题

拦截导弹

https://ac.nowcoder.com/acm/problem/16810

拦截导弹

https://ac.nowcoder.com/acm/problem/16810

涉及算法:最长递增子序列(LIS)。dp[i]表示以第i个元素结尾的最长递增子序列的长度。数组中每个元素对于本身可以构成一个递增序列,所有初始化dp为1,然后循环取判断每个元素与在它之前的元素比较,前面的元素小于它,则说明可以放在该元素后面,然后再判断dp[i]与dp[j] + 1的大小,如果小于他没必要放在这个元素后面,这样也就可以求出最大值来。最长不递增子序列也是同样的道理。
分析:最长不递增的序列个数等于最长递增序列,先用一个dp算出最长不递增序列的长度,类似的可以算出最长递增序列的长度。

#include <bits/stdc++.h>
#include <iostream>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
const int mod = 1e9+7;
//const int inx = INT_MAX; 
using namespace std;
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

//定义i i(A) i+n i+n(B) i+n+n i+n+n(C) 
//bitset<Max>s,q;

int dp1[100005];
int dp2[100005];
int a[100005];
int main()
{
    int i,j,n,t;
    int x,ans = 0,ans1 = 0;
    t = 0;
    while(cin >> x){
        a[++t] = x;
    }
    for(i = 1; i <= t; i++) dp1[i] = 1,dp2[i] = 1;
    for(i = 1; i <= t; i++){
        for(j = 1; j < i; j++){
            if(a[i] <= a[j] && dp1[i] <= dp1[j] + 1){
                dp1[i] = dp1[j] + 1;
            }
        }
        ans = max(ans,dp1[i]);
    }
    cout << ans << endl;
    for(i = 1; i <= t; i++){
        for(j = 1; j < i; j++){
            if(a[i] > a[j] && dp2[i] < dp2[j] + 1){
                dp2[i] = dp2[j] + 1;
            }
        }
        ans1 = max(ans1,dp2[i]);
    }
    cout << ans1;
    return 0;
}



被3整除的子序列

https://ac.nowcoder.com/acm/problem/21302
思路(个人理解):
1:一个数能够被3整除说明这个数所有位上的数之和为3的倍数,那么我们就去对每位上的数求和,对3取模,我们会的到0,1,2,取模为0的就是我们要的答案,现在就是要找到有多少个序列取模为零。
2:考虑dp[i][j],表示0-i组成的子序列中,数模3位j的个数有多少个,然后考虑转移方程,dp[i][j]可以有前i-1个转移过来,考虑第i个数字加不加上去,若不加上去则dp[i][j] = dp[i-1][j],也就是前i个数组成的子序列中,数模3位j的个数有多少个,和i-1一样,若加上去,则dp[i][j] = dp[i-1][(j-m+3)%3](m=a[i]%3),也就是前i-1个数组成的序列取模后的数加上m后取模的数有多少个。**还有dp[i][m] += 1,自己也可以是一个序列**。
3:综合**dp[i][j] = (dp[i-1][j]+dp[i-1][(j-m+3)%3]) % mod,dp[i][m] += 1**.

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
using namespace std;

//781
LL dp[55][3];//dp[i][j]表示前i个数中所有子序列和取模为j的个数
int main()
{
    char s[55];
    int len;
    cin >> s;
    len = strlen(s);
    for(int i = 0; i < len; i++){
        int temp;
        temp = (s[i] - '0') % 3;
        for(int j = 0; j <= 2; j++){
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][(j - temp + 3) % 3]) % mod;
        }
        dp[i][temp] = (dp[i][temp] + 1) % mod;
    }
    cout << dp[len - 1][0];
    return 0;
}


牛牛与数组

思路:
1:动态规划先找状态,再找初始值,然后状态转移,最后确定答案。
2:这道题给了我们数组的限制长度,那么我们可以由更短的数组长度来推到更长的数组长度,考虑数组长度减一满足条件的有多少组。给出状态dp[i][j]表示数组长度为i以数j结尾的满足条件的有多少个。
3:状态转移:dp[i][j] = dp[i-1][m](1<=m<=j&&j%m!=0),然后去枚举,但是我们发现枚举时间复杂度为O(k*k),不能过。
4:考虑dp优化,条件1<=m<=j&&j%m!=0,那我们就去枚举长度为i-1的数组以j的倍数结尾的有多少个,减去就可以了,总体时间复杂的为:O(n*k*sqrt(k))。
超时代码O(n*k*k):
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
using namespace std;

//781
int dp[10][100005];//dp[i][j]表示长度为i的数中以j结尾的数组个数
int main()
{
    int n,k;
    cin >> n >> k;
    for(int i = 1; i <= k; i++) dp[1][i] = 1;
    for(int i = 2; i <= n; i++){
        LL sum = 0,sum1;
        for(int j = 1; j <= k; j++){
            //sum = (sum + dp[i - 1][j]) % mod;//表示长度为i-1的数中以j结尾的数组个数
        for(int p = 1; p <= k; p++){
            if(p <= j || (p % j) != 0){
                dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
            }
        }
        }
    }
    LL cnt = 0;
    for(int i = 1; i <= k; i++){
        cnt = (cnt + dp[n][i]) % mod;
    }
    cout << cnt;
    return 0;
}


正确AC代码O(n*k*sqrt(n))
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
using namespace std;

//781
int dp[15][100005];//dp[i][j]表示长度为i的数中以j结尾的数组个数
int main()
{
    int n,k;
    cin >> n >> k;
    for(int i = 1; i <= k; i++) dp[1][i] = 1;
    for(int i = 2; i <= n; i++){
        LL sum = 0,sum1;
        for(int j = 1; j <= k; j++){
            sum = (sum + dp[i - 1][j]) % mod;//表示长度为i-1的数中以j结尾的数组个数
        }
        for(int j = 1; j <= k; j++){
            sum1 = 0;
            for(int p = j+j; p <= k; p += j){
                sum1 = (sum1 + dp[i - 1][p]) % mod;//计算长度为i-1的数中以j的倍数结尾的数组个数
            }
            dp[i][j] = (sum - sum1) % mod;
        }
    }
    LL cnt = 0;
    for(int i = 1; i <= k; i++){
        cnt = (cnt + dp[n][i]) % mod;
    }
    cout << cnt;
    return 0;
}

摆花

思路:
1:题目说了花的种类顺序是按序号从小到大排的,所有我们从前往后推。
2:状态 dp[i][j]:表示前i种花摆j盆花出来的方案数。
3: 转移方程:dp[i][j] = dp[i-1][j](不摆第i种花)dp[i][j] = dp[i-1][j-1]+...+dp[i-1][j-a[i]](摆第i种花,第i种花的数量是1-a[i])
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e6+7;
const LL INF = 1e18;
using namespace std;

//781
LL dp[505][505];//dp[i][j]表示前i种花摆j盆的方案数。
int a[505];
//dp[i][j] = dp[i-1][j] + dp[i-1][j-1]+...+dp[i-1][j-a[i]];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    //for(int i = 0; i <= n; i++) dp[i][0] = 1;
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            for(int k = 0; k <= a[i] && k <= j; k++){
                dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod;
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

Training Plan

思路:dp[i][j]:表示第i天刷j道题的最小难度。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
const LL INF = 1e18;
using namespace std;
 
//781
LL dp[505][505];//dp[i][j]表示第i天刷j道题的最小难度。
LL a[505];
int main()
{
    int t,n,m;
    cin >> t;
    while(t--){
        cin >> n >> m;
        memset(a,0,sizeof(a));
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a+1,a+n+1);
        for(int i = 1; i <= n; i++) dp[1][i] = (a[i] - a[1]) * (a[i] - a[1]);
        for(int i = 2; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = INF;
                for(int k = 1; k < j; k++){
                dp[i][j] = min(dp[i][j],dp[i-1][k] + (a[j]-a[k+1])*(a[j]-a[k+1]));
                }
            }
        }
        LL ans = INF;
        for(int i = 0; i <= n; i++){
            ans = min(dp[m][i],ans);
        }
        cout << dp[m][n] << endl;
    }
    return 0;
}


购物

思路:
1:状态dp[i][j]表示前i天买j个糖果的最少钱。
2:对于每一天要买的糖果我们优先买价格少的,因为要买k个,所有我们提前算出每天糖果价钱的前缀和sum[i][j].
3:转移方程:dp[i][j] = min(dp[i][j],dp[i-1][j-k]+sum[i][k]+k*k).
4:因为要保证每天都有糖果吃,所有到第i天买的所有糖果数必须超过i个,所有到第i天j从i开始枚举到m。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
const int INF = 1e6;
using namespace std;

//781

int dp[505][505];//dp[i][j]表示前i天买j个糖果的最少钱。
int a[505][505];
int sum[505][505];
//dp[i][j] = dp[i-1][j] + dp[i-1][j-1]+...+dp[i-1][j-a[i]];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            dp[i][j] = INF;
        }
        sort(a[i]+1,a[i]+m+1);
        for(int j = 1; j <= m; j++) sum[i][j] = sum[i][j-1] + a[i][j];
    }
    memset(dp,1e6,sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            for(int k = 0; k <= j && k <= m; k++){
            dp[i][j] = min(dp[i][j],dp[i-1][j-k]+sum[i][k]+k*k);
            }
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}

取数游戏

思路1:
1:状态dp[i][j][0/1]:表示前i次有j次是取左端的数,然后第i次是取左端/右端的(0/1)
2:转移方程
if(j) dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j-1][1],dp[i-1][j-1][0])+a[j]*b[i]);
dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j][0], dp[i-1][j][1]) + b[i]*a[n-i+j+1]);
思路2:
1:状态:dp[i][j]表示区间i-j的最优解
2:转移方程:dp[i][j] = max(dp[i+1][j]+a[i]*b[k],dp[i][j-1]+a[j]*b[k])
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
const int INF = 1e6;
using namespace std;
 
//781
 
int dp[1005][1005][2];//dp[i][j][0/1]1表示选了i个数中j个是左端点,0是右端点。
int a[1005],b[1005];
int main()
{
    int t,n;
    cin >> t;
    while(t--){
        cin >> n;
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cin >> b[i];
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= i; j++){
                if(j) dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j-1][1],dp[i-1][j-1][0])+a[j]*b[i]);
                dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j][0], dp[i-1][j][1]) + b[i]*a[n-i+j+1]);
            }
        }
        int Max = 0;
        for(int i = 0; i <= n; i++){
            Max = max(Max,dp[n][i][1]);
            Max = max(Max,dp[n][i][0]);
        }
        cout << Max << endl;
    }
    return 0;
}

矩阵快速幂:

https://ac.nowcoder.com/acm/contest/1168/K

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define ll long long
#define inf 0x3f3f3f3f
const int mod = 666666;
using namespace std;

struct matrix{
	ll m[2][2];
	matrix(){
	memset(m,0,sizeof(m));	
	};
};

matrix cf(matrix a,matrix b)
{
	matrix temp;
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			for(int k = 0; k < 2; k++){
				temp.m[i][j] = (temp.m[i][j] + a.m[i][k]*b.m[k][j]) % mod;
			}
		}
	}
	return temp;
}

matrix qpow(matrix a,int n)
{
	matrix res;
	for(int i = 0; i < 2; i++) res.m[i][i] = 1;
	while(n){
		if(n & 1) res = cf(res,a);
		a = cf(a,a);
		n >>= 1;
	}
	return res;
}

int main()
{
	ll n,m;
	matrix a;
	while(cin >> n >> m){
		a.m[0][0] = 4;
		a.m[0][1] = 3;
		a.m[1][0] = 1;
		a.m[1][1] = 0;
		ll ans;
		a = qpow(a,n - 2);
		ans = (a.m[0][0]*233 % mod + a.m[0][1]*4 % mod) % mod;
		ans = m - ans;
		cout << ans << endl;
	}
	return 0;
}

最大子矩阵和:

先看一维的:核心代码dp[i] = max(dp[i - 1] + a[i],a[i]),dp[i]表示以第i个元素结尾的子矩阵的最大和。
//这样写方便找出最大值
int getmax(int a[],int n)
{
    int i,s = 0,m = a[0];
    for(i = 0; i < n; i++)
    {
        if(s >= 0) s += a[i];
        else s = a[i];
        if(s > m) m = s;
    }
    return m;
}
二维:我们可以先把二维的转化成一维的再按一维求最大子矩阵和,如何转化,我们可以通过行或列的压缩,我们按行压缩,将多行压缩成一行。
如:
1 -1 2
4 9 15
-7 1 10
取第一行:1 -1 2 m = 2
再加上第二行: 5 8 17 m = 30
再加上第三行: -2 9  27 m = 34
取第二行: 4 9 15 m = 28
...
这样可以把所有能构成的子矩阵全部搞出来。
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int getmax(int a[],int n)
{
    int i,s = 0,m = a[0];
    for(i = 0; i < n; i++)
    {
        if(s >= 0) s += a[i];
        else s = a[i];
        if(s > m) m = s;
    }
    return m;
}
int main()
{
    int N;
    while(~scanf("%d",&N))
    {
        int i,j,k;
        int sum[105];
        int a[105][105];
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                 scanf("%d",&a[i][j]);
                int n = a[0][0];
        for(i = 0; i < N; i++)//先取第i行。
        {
            memset(sum,0,sizeof(sum));
            for(j = i; j < N; j++)//在取了第i行的基础上加上第j行
            {
                for(k = 0; k < N; k++)
                {
                    sum[k] += a[j][k];
                }
                int m = getmax(sum,N);
                if(m > n) n = m;
            }
        }
        printf("%d\n",n);
    }
    return 0;
}

数字和为sum的方法数:01背包变形

思路:看题目意思应该相同下标不同顺序算一种。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
const ll res = 233; 

using namespace std;

ll dp[1005];//dp[i][j]表示前i个数中组成和为j的种类数
int sum,a[1005];
int main()
{
	int n;
	cin >> n >> sum;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	memset(dp,0,sizeof(dp));
	dp[0] = 1;//组成0,即不取一种 
	for(int i = 1; i <= n; i++){
		for(int j = sum; j >= a[i]; j--){
			dp[j] = dp[j] + dp[j - a[i]];//和01背包的不同之处,01背包是dp[j] = max(dp[j],dp[j-a[i]);
		}
	}
	cout << dp[sum] << endl;
	return 0;
}

宵暗的妖怪

比赛链接:https://ac.nowcoder.com/acm/contest/8755#question
思路:
动规三步:
1)找状态:dp[i][0]表示从下标1开始,并以下标i结尾的区间,不吞噬第i个数的最大饱食度,同理dp[i][1]表示吞噬第i个数的最大饱食度。根据题意可知,如果吞噬了i,那么i-1,i-2也会被吞噬。
2)状态转移:dp[i][0] = max(dp[i-1[0],dp[i-1][0], dp[i][1] = dp[i-2][0]+a[i-1]
3)初始化:我们要从第三个数开始,因为每次要连续吞噬三个,而我们的i表示吞噬的是这三个中的最后一个。如果小于三,那么就是0.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
  
using namespace std;

ll dp[100005][3];
int a[100005];
int main()
{
	int n,x;
	cin >> n;
	cin >> a[1] >> a[2];
	for(int i = 3; i <= n; i++){
		cin >> a[i];
		dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
		dp[i][1] = dp[i-2][0]+a[i-1];
	} 
	cout << max(dp[n][1],dp[n][0]) << endl;
	return 0;
}

第十届蓝桥杯国赛 B题

题面:
2019可以被分解成若干个两两不同的素数,请问不同的分解方案有多少种?
注意:分解方案不考虑顺序,如2+2017=2019和2017+2=2019属于同一种方案。
解法同上
这种解法看上去好像会有2+2017,2017+2这种类似的重复,其实是没有的,因为这些素数是从小到大排列好了的,而且是选完前面的在选后面的,所有不会出现这种重复情况。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
//const double p = 3.141592653589793238462643383;
const ll res = 233; 

using namespace std;

ll dp[2020];
int prime[2020],vis[2020],cnt = 0;
void getprime()
{
	for(int i = 2; i <= 2019; i++){
		if(!vis[i]){
			vis[i] = i;
			prime[cnt++] = i;
		}
		for(int j = 0; j < cnt; j++){
			if(i*prime[j] > 2019) break;
			vis[i*prime[j]] = prime[j];
			if(i%prime[j] == 0) break;
		}
	}
}

int main()
{
	int n;
	getprime();
	memset(dp,0,sizeof(dp));
	dp[0] = 1;//不取 
	for(int i = 0; i < cnt; i++){
		for(int j = 2019; j >= prime[i]; j--){
			dp[j] = dp[j] + dp[j - prime[i]];
		}
	}
	cout << dp[2019] << endl;
	return 0;
}
//答案:55965365465060

第十届蓝桥杯国赛 F题:dp

题面:

题目给定两个字符串S和T,保证S的长度不小于T的长度,问至少修改S的多少个字符,可以令T成为S的子序列。

输入描述:

两行。
第一行是字符串S,第二行是字符串T。
保证S的长度不小于T的长度,S的长度范围在10~1000之间。

输出描述:

答案,一个非负整数。

输入样例:

XBBBBBAC
ACC

输出样例:

2
思路:
1)状态:dp[i][j] 表示,使t串前j段中成为s串的前i段的子序列的修改字符次数。
2)初值:初始化当j=0和i=j的情况
3)状态转移:
if (s[i] == t[j]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1);


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
//const double p = 3.141592653589793238462643383;
const ll res = 233; 
 
using namespace std;
 
int dp[1005][1005];
int main()
{
    int l1,l2;
    string s,t;
    cin >> s >> t;
    l1 = s.size();
    l2 = t.size();
   // memset(dp,0x3f3f,sizeof(dp));
    if(s[0] != t[0]) dp[0][0] = 1;
    for(int i = 1; i < l1; i++){
        if(s[i] != t[0]) dp[i][0] = dp[i-1][0];
        else dp[i][0] = 0;
    }
    for(int i = 1; i < l2; i++){
        if(s[i] != t[i]) dp[i][i] = dp[i-1][i-1]+1;
        else dp[i][i] = dp[i-1][i-1];
    }
    for(int j = 1; j < l2; j++){
        for(int i = j+1; i < l1; i++){
           // if(i == 0 || j == 0) continue;
            if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min(dp[i-1][j-1]+1,dp[i-1][j]);
        }
    }
    cout << dp[l1-1][l2-1] << endl;
}
		





全部评论

相关推荐

头像
11-09 17:30
门头沟学院 Java
TYUT太摆金星:我也是,好几个华为的社招找我了
点赞 评论 收藏
分享
服从性笔试吗,发这么多笔,现在还在发。
蟑螂恶霸zZ:傻 x 公司,发两次笔试,两次部门匹配挂,
投递金山WPS等公司10个岗位 >
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务