动态规划

乐***对
题目https://ac.nowcoder.com/acm/contest/6874/B

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    vector<int>p(n+1);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
    }
    vector<int>dp(n+1);
    int ans=0;
    sort(p.begin()+1,p.end());//按能力值排序
    dp[0]=0;//p[i]为人数为i是最大组对数
    for(int i=1;i<=n;i++){
        if(i<p[i])ans=0;//人数小于能力值，ans为0
        else ans=dp[i-p[i]]+1;
        dp[i]=max(ans,dp[i-1]);
    }
    if(!ans)ans=-1;
    printf("%d",ans);
}

分组
题目https://ac.nowcoder.com/acm/problem/24190

# include <cstdio>
# include <iostream>
# include <algorithm>
using namespace std;
const int N=10005;
int n,k,a[N],f[N];

int main () {
    scanf ("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf ("%d",&a[i]);
    for (int i=1;i<=n;i++) {
        int sum=-1e9;
        for (int j=i;i-j+1<=k&&j>=1;j--) {//这里注意一下，j不仅要保证在k个以内，还要大于等于1
            sum=max(sum,a[j]);
            f[i]=max(f[i],f[j-1]+sum*(i-j+1));
        }
    }
    printf ("%d\n",f[n]);
    return 0;
}

青蛙
题目https://ac.nowcoder.com/acm/contest/8417/G

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
const int N = 3e3+500;
const int inf = -0xfffffff;
using namespace std;
vector<vector<int>>a(N, vector<int>(N,inf));
int main()
{
    ios;
    int n;
    cin >> n;
    int start = n;
    int i;
    for (i = 1; i <= n; i++) {
        for (int j = start; j <= n+i-1; j += 2) {
            if (i == 1)cin >> a[i][j];
            else {
                cin >> a[i][j];
                a[i][j] += max({a[i - 1][j - 1], a[i - 1][j + 1], a[i-2][j]});
            }
        }
        start--;
    }
    start = 2;
    for (; i <= 3 * n - 3; i++) {
        for (int j = start; j <= 2*n-start; j += 2) {
            cin >> a[i][j];
            a[i][j] += max({a[i - 1][j - 1], a[i - 1][j + 1], a[i-2][j]});
        }
        if (start == 2)start = 1;
        else start = 2;
    }
    start = 1;
    for (; i <= 4 * n - 3; i++) {
        for (int j = start; j <= 2*n - start; j += 2) {
            if (i == 1)cin >> a[i][j];
            else {
                cin >> a[i][j];
                a[i][j] += max({a[i - 1][j - 1], a[i - 1][j + 1], a[i-2][j]});
            }
        }
        start++;
    }
    cout << a[4 * n - 3][n] << endl;
}