acm之旅--保研练习系列-程序员宅基地

技术标签： ACM  

文章目录


题目链接： 保研练习系列

A - Max Sum Plus Plus

题目链接：A - Max Sum Plus Plus
参考博文：Max Sum Plus Plus （动态规划+m子段和的最大值）

  • 思路：
    • 状态构造：dp[i][j]表示前j个数分成i组（第j个数字一定在组内）的最大和。
    • max(dp[m][j])
    • 动态转移方程：dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][k])+a[j]) (0<k<j)。
      dp[i][j-1]+a[j]表示的是前j-1分成i组，第j个必须放在前一组里面。
      max( dp[i-1][k] ) + a[j] )表示的前（0<k<j）分成i-1组，第j个单独分成一组。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 1000005;
int dp[MAX], a[MAX];
int Max[MAX];

int main()
{
    
    int n, m;
    while(cin >> m >> n)
    {
    
        for(int i=1; i<=n; i++)
        cin >> a[i];
        memset(dp, 0, sizeof(dp));
        memset(Max, 0, sizeof(Max));
        int mmax;//表示当前最大值
        for(int i=1; i<=m; i++)
        {
    
            mmax = -1<<29;
            for(int j=i; j<=n; j++)
            {
    
                dp[j] = max(dp[j-1]+a[j], Max[j-1]+a[j]);
                Max[j-1] = mmax;//更新后用于下一个i循环，代表max(dp[i-1][k])
                mmax = max(mmax, dp[j]);//一直保持在前
            }
        }
        cout << mmax << endl;
    }
    return 0;
}
B - Ignatius and the Princess IV

题目链接：B - Ignatius and the Princess IV

  • 思路：水题。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

typedef long long LL;
map<LL, LL> m;
int main()
{
    
    int N;
    LL a, ans;
    while(scanf("%d", &N)!=EOF)
    {
    
        m.clear();
        int res = (N+1)/2;
        for(int i=0; i<N; i++)
        {
    
            scanf("%lld", &a);
            m[a]++;
            if(m[a]==res) ans = a;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
C - Monkey and Banana

题目链接：C - Monkey and Banana

  • 思路：这是《算法竞赛入门（第二版）》中的一道题，具体见中的437题。难点在与状态的构造，使用维这一个变量，简化的方法。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int a[50][5], dp[50][5], n;

void Init(int n)
{
    
    for(int i=0; i<=n; i++)
    {
    
        for(int j=0; j<3; j++)
            dp[i][j] = 0;
    }
}
bool check(int i, int j, int k, int t)
{
    
    vector<int> m1, m2;
    for(int h=0; h<3; h++)
    {
    
        if(h!=j) m1.push_back(a[i][h]);
        if(h!=t) m2.push_back(a[k][h]);
    }
    if(m1[0]<=m2[0] || m1[1]<=m2[1]) return 0;
    else                             return 1;
}
int DP(int i, int j)
{
    
    int &ans = dp[i][j];
    if(ans>0) return ans;
    ans = a[i][j];
    for(int k=1; k<=n; k++)
    {
    
        for(int t = 0; t<3; t++)
        {
    
            if(check(i, j, k, t))
            {
    
                ans = max(ans, DP(k, t)+a[i][j]);
            }
        }
    }
    return ans;
}
int main()
{
    
    int kase = 1;
    while(scanf("%d", &n)!=EOF && n)
    {
    
        for(int i=1; i<=n; i++)
        {
    
            scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
            sort(a[i], a[i]+3);
        }
        Init(n);
        int Max = 0;
        for(int i=1; i<=n; i++)
        {
    
            for(int j=0; j<3; j++)
            {
    
                Max = max(Max, DP(i, j));
            }
        }
        printf("Case %d: maximum height = %d\n", kase++, Max);
    }
    return 0;
}
D - Doing Homework

题目链接：D - Doing Homework

E - Super Jumping! Jumping! Jumping!

题目链接：E - Super Jumping! Jumping! Jumping!

  • 思路：LIS的简单变体，由求最长递增子序列的长度变为求最长递增子序列的和，套用即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    
    int N, a[1005], dp[10005];
    while(cin >> N && N)
    {
    
        for(int i=1; i<=N; i++)
            cin >> a[i];
        memset(dp, 0, sizeof(dp));
        a[0] = -1<<29;
        int ans = 0;
        for(int i=1; i<=N; i++)
        {
    
            for(int j=0; j<i; j++)
            {
    
                if(a[j]<a[i])
                    dp[i] = max(dp[i], dp[j]+a[i]);
            }
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}
F - Piggy-Bank

题目链接：F - Piggy-Bank

  • 思路：一个完全背包的模板题，注意数组不要开小了。。。。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int INF = 1<<29;
struct Node
{
    
    int p, w;
};
Node coin[1000];
int dp[10005];//注意数组大小，开小了可能TLE

int main()
{
    
    int T, E, F, N, n;
    scanf("%d", &T);
    while(T--)
    {
    
        scanf("%d%d", &E, &F);
        N = F-E;
        scanf("%d", &n);
        fill(dp, dp+N+1, INF);
        dp[0] = 0;
        for(int i=1; i<=n; i++)
        {
    
            scanf("%d%d", &coin[i].p, &coin[i].w);
            for(int j=coin[i].w; j<=N; j++)
            {
    
                dp[j] = min(dp[j], dp[j-coin[i].w]+coin[i].p);
            }
        }
        if(dp[N]==INF)
            printf("This is impossible.\n");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[N]);
     }
    return 0;
}
G - 免费馅饼

题目链接：G - 免费馅饼
参考博文： G. 免费馅饼

  • 思路：动态规划题目。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int a[100005][11], dp[100005][11];//a[i][j]为第i秒的j位置掉下的馅饼数量,dp[i][j]表示第i秒在j位置总共接了多少个馅饼
int dx[5] = {
    -1, 0, 1};
int DP(int i, int j)
{
    
    int &ans = dp[i][j];
    if(ans>0 || i==1) return ans;
    int st = 0, ed = 3;
    if(j==0) st = 1;
    else if(j==10) ed = 2;
    for(int k=st; k<ed; k++)
    {
    
        ans = max(ans, DP(i-1, j+dx[k])+a[i][j]);
    }
    return ans;
}
int main()
{
    
    int n, b, c;
    while(scanf("%d", &n)!=EOF && n)
    {
    
        int T = 0;
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
    
            scanf("%d%d", &b, &c);
            a[c][b]++;
            if(T<c) T = c;
        }
        dp[1][4] = a[1][4], dp[1][5] = a[1][5], dp[1][6] = a[1][6];
        int Max = 0;
        for(int j=0; j<=10; j++)
        {
    
            Max = max(Max, DP(T, j));
        }
        printf("%d\n", Max);
    }
    return 0;
}
H - Tickets

题目链接：H - Tickets

  • 思路：
    • 状态构造：dp[i]表示前i个人所需取票的时间。
    • 终态：dp[K]，K为总人数。
    • 状态转移方程：dp[i] = min(dp[i-1]+a[i], dp[i-2]+b[i-1])，a[i]表示第i个人取票的时间，b[i-1]表示第i-1和第i个人一起取票的时间。
    • 初始化：dp[0] = 0.
      我使用了记忆化搜索。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int MAX = 5000;
int a[MAX], b[MAX], dp[MAX];
int DP(int i)
{
    
    if(i<0) return 0;//注意i<0的情况
    int &ans = dp[i];
    if(ans!=-1) return ans;
    if(i>1) ans = min(DP(i-1)+a[i], DP(i-2)+b[i-1]);
    else    ans = a[i];//i==1时，为a[1]
    return ans;
}
int main()
{
    
    int N, K;
    scanf("%d", &N);
    while(N--)
    {
    
        vector<int> ans;
        scanf("%d", &K);
        for(int i=1; i<=K; i++)
        {
    
            scanf("%d", &a[i]);
        }
        for(int i=1; i<K; i++)
        {
    
            scanf("%d", &b[i]);
        }
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        int t = DP(K);
        //换算时间
        int h = t/3600+8;
        t = t%3600;
        int m = t/60;
        t = t%60;
        printf("%02d:%02d:%02d ", h, m, t);
        if(h>=12) printf("pm");//中午12点是pm，晚上12点是am
        else      printf("am");
        printf("\n");
    }
    return 0;
}
I - 最少拦截系统

题目链接：I - 最少拦截系统

  • 思路：类似于最长非增子序列，但是需要求非增子序列的最少个数，因此可以使用一个数组d来存储每一个非增子序列的末尾元素，如果当前元素小于等于其中的元素，则更新最接近它的元素，如果均小于它，则将该元素添加到数组中，最后数组的大小即为所求。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int MAX = 500000;
int a[MAX], dp[MAX];
vector<int> d;//记录每一个非增子序列的末尾元素,更新时一定是从小到大排好序
int main()
{
    
    int n;
    while(scanf("%d", &n)!=EOF)
    {
    
        d.clear();
        for(int i=1; i<=n; i++)
            scanf("%d", &a[i]);
        fill(dp, dp+n+1, 1);
        d.push_back(a[1]);
        for(int i=2; i<=n; i++)
        {
    
            int j;
            for(j=0; j<d.size(); j++)
            {
    
                if(d[j]>=a[i])//表明a[i]可以加入d[j]结尾的序列中，因此更新末尾元素
                {
    
                    d[j] = a[i];
                    break;
                }
            }
            if(j==d.size()) dp[i] = dp[i-1]+1, d.push_back(a[i]);//表明没有更新
            else            dp[i] = dp[i-1];
        }
        printf("%d\n", d.size());
    }
    return 0;
}
J - FatMouse’s Speed

题目链接：J - FatMouse’s Speed

  • 思路：保证按重量递增但是同时速度递减，则可以先按重量从小到大排序，然后就是对于速度的最大递减子序列，但是需要记录序列，可以使用pre数组记录路径。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

struct Node
{
    
    int w, s, id;
    bool operator < (const Node &A) const
    {
    
        if(w==A.w) return s>A.s;
        else       return w<A.w;
    }
};
Node M[2000];
int pre[10005], dp[2000];//dp表示前i个的子序列长度

int main()
{
    
    int cnt = 1;
    while(scanf("%d%d", &M[cnt].w, &M[cnt].s)!=EOF)
    {
    
        M[cnt].id = cnt;
        cnt++;
    }
    sort(M+1, M+cnt);
    fill(dp, dp+cnt+1, 1);
    memset(pre, 0, sizeof(pre));
    for(int i=1; i<cnt; i++)
    {
    
        for(int j=1; j<i; j++)
        {
    
            if(M[j].w<M[i].w && M[j].s>M[i].s)//严格
            {
    
                if(dp[i]<dp[j]+1)
                {
    
                    dp[i] = dp[j]+1;
                    pre[i] = j;
                }
            }
        }
    }
    int Max = 0, idx;
    for(int i=1; i<cnt; i++)
    {
    
        if(Max<dp[i])
        {
    
            Max = dp[i];
            idx = i;//找出末尾下标
        }
    }
    vector<int> ans;
    ans.push_back(M[idx].id);//存储原始编号
    while(pre[idx])
    {
    
        idx = pre[idx];//反向寻找路径
        ans.push_back(M[idx].id);
    }
    printf("%d\n", Max);
    for(int i=ans.size()-1; i>=0; i--)
        printf("%d\n", ans[i]);
    return 0;
}
K - Jury Compromise

题目链接：K - Jury Compromise

  • 思路：
L - Common Subsequence

题目链接：L - Common Subsequence

  • 思路：裸的LCS。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 1000;
int dp[MAX][MAX];
int main()
{
    
    string s1, s2;
    while(cin >> s1 >> s2)
    {
    
        int n = s1.size(), m = s2.size();
        s1 = " "+s1, s2 = " "+s2;
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
    
            for(int j=1; j<=m; j++)
            {
    
                if(s1[i]==s2[j])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        printf("%d\n", dp[n][m]);
    }
    return 0;
}
M - Help Jimmy

题目链接：M - Help Jimmy
参考博文：M - Help Jimmy DP

  • 思路：好题。首先垂直高度一定为Y，不需要考虑，而水平方向需要考虑向左还是向右。
    首先将板子按高度从小到大排序，且起始点为高度为Y，长度为0的板子，则起始点一定是最后一个板子。
    • 状态构造：dp[i][0]表示在第i个板子上向左走（到地面）的水平时间，dp[i][1]表示在第i个板子上向右走（到地面）的水平时间。
    • 终态：dp[n][0]，表示起始点的水平时间。
    • 状态转移方程：
      • d p [ i ] [ 0 ] = m i n ( d p [ l p ] [ 0 ] + a [ i ] . l − a [ l p ] . l , d p [ l p ] [ 1 ] + a [ l p ] . r − a [ i ] . l ) dp[i][0] = min(dp[lp][0]+a[i].l-a[lp].l, dp[lp][1]+a[lp].r-a[i].l) dp[i][0]=min(dp[lp][0]+a[i].l−a[lp].l,dp[lp][1]+a[lp].r−a[i].l);lp表示从第i个板子左边掉落可以到达的板子的下标，a[i].l表示第i个板子的左边缘的水平坐标，a[i].r表示第i个板子的右边缘的水平坐标。
      • d p [ i ] [ 1 ] = m i n ( d p [ r p ] [ 0 ] + a [ i ] . r − a [ r p ] . l , d p [ r p ] [ 1 ] + a [ r p ] . r − a [ i ] . r ) dp[i][1] = min(dp[rp][0]+a[i].r-a[rp].l, dp[rp][1]+a[rp].r-a[i].r) dp[i][1]=min(dp[rp][0]+a[i].r−a[rp].l,dp[rp][1]+a[rp].r−a[i].r);
    • dp[][] = INF
      需要考虑高度是否可以落下，如果不可以则为INF。具体见代码

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1<<29;
const int MAX = 1005;

struct Node
{
    
    int l, r, h;
}a[MAX];
int dp[MAX][2];
bool cmp(Node a, Node b)
{
    
    return a.h<b.h;
}
void Init(int n)
{
    
    for(int i=0; i<=n+1; i++)
    {
    
        for(int j=0; j<2; j++)
            dp[i][j] = INF;
    }
}
int main()
{
    
    int t, n, x, y, d;
    scanf("%d", &t);
    while(t--)
    {
    
        scanf("%d%d%d%d", &n, &x, &y, &d);
        Init(n);
        for(int i=0; i<n; i++)
        {
    
            scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].h);
        }
        a[n].l = a[n].r = x;
        a[n].h = y;
        sort(a, a+n, cmp);//按高度从小到大
        for(int i=0; i<=n; i++)
        {
    
            int lp = -1, rp = -1;//分别为左边和右边板子的编号
            for(int j=i-1; j>=0; j--)//从高度比i低的板子中选择左右板子
            {
    
                if(lp==-1 && a[j].l<=a[i].l && a[j].r>=a[i].l)
                {
    
                    lp = j;
                }
                if(rp==-1 && a[j].r>=a[i].r && a[j].l<=a[i].r)
                {
    
                    rp = j;
                }
            }
            if(lp==-1)//当不存在左边的板子
            {
    
                if(a[i].h<=d) dp[i][0] = 0;//可以直接落到地上
                else          dp[i][0] = INF;//这边不可以落下
            }
            if(rp==-1)
            {
    
                if(a[i].h<=d) dp[i][1] = 0;
                else          dp[i][1] = INF;
            }
            if(lp!=-1 && a[i].h-a[lp].h<=d)//左边的板子可以落下
                dp[i][0] = min(dp[lp][0]+a[i].l-a[lp].l, dp[lp][1]+a[lp].r-a[i].l);
            if(rp!=-1 && a[i].h-a[rp].h<=d)
                dp[i][1] = min(dp[rp][0]+a[i].r-a[rp].l, dp[rp][1]+a[rp].r-a[i].r);
        }
        printf("%d\n", dp[n][0]+y);
    }
    return 0;
}
N - Longest Ordered Subsequence

题目链接：N - Longest Ordered Subsequence

  • 思路：裸的LIS。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[10005], dp[10005];

int main()
{
    
    int N;
    scanf("%d", &N);
    fill(dp, dp+N+1, 1);
    int ans = 0;
    for(int i=1; i<=N; i++)
    {
    
        scanf("%d", &a[i]);
        for(int j=1; j<i; j++)
        {
    
            if(a[j]<a[i])
                dp[i] = max(dp[i], dp[j]+1);
        }
        if(ans<dp[i]) ans = dp[i];
    }
    printf("%d\n", ans);
    return 0;
}
O - Treats for the Cows

题目链接：O - Treats for the Cows
＊ 思路：一开始看了样例以为是贪心，但是有反例。实则是区间DP。区间DP一般循环时外层都是区间长度。
* 状态构造：dp[i][j]表示序列的第i个到第j个的最大价值。
* 终态：dp[1][N]。
* 状态转移方程： d p [ i ] [ j ] = m a x ( d p [ i + 1 ] [ j ] + a [ i ] ∗ ( N − ( j − i ) ) , d p [ i ] [ j − 1 ] + a [ j ] ∗ ( N − ( j − i ) ) ) dp[i][j] = max(dp[i+1][j]+a[i]*(N-(j-i)), dp[i][j-1]+a[j]*(N-(j-i))) dp[i][j]=max(dp[i+1][j]+a[i]∗(N−(j−i)),dp[i][j−1]+a[j]∗(N−(j−i)))，表示取首部和取尾部的最大值。
* 初始化：dp[i][i] = a[i]*N。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

typedef long long LL;
const int MAX = 2005;
LL a[MAX], dp[MAX][MAX];

int main()
{
    
    int N;
    scanf("%d", &N);
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=N; i++)
    {
    
        scanf("%d", &a[i]);
        dp[i][i] = a[i]*N;
    }
    for(int len = 2; len<=N; len++)
    {
    
        for(int i=1; i<=N; i++)
        {
    
            int j=i+len-1;
            if(j>N) break;
            dp[i][j] = max(dp[i+1][j]+a[i]*(N-(j-i)), dp[i][j-1]+a[j]*(N-(j-i)));
        }
    }
    printf("%lld\n", dp[1][N]);
    return 0;
}
P - FatMouse and Cheese

题目链接：P - FatMouse and Cheese

  • 思路：注意看题意，是只能水平跑或垂直跑。类似于滑雪问题，只不过范围扩大了，依然可以使用记忆化搜索。dp[x][y]表示在(x,y)处可以吃到的最多的奶酪。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int n, k;
int G[105][105];
int dp[105][105];
int dx[5] = {
    0, 0, 1, -1};
int dy[5] = {
    1, -1, 0, 0};

int DP(int x, int y)
{
    
    int &ans = dp[x][y];
    if(ans!=-1) return ans;
    ans = G[x][y];
    for(int i=1; i<=k; i++)//步数
    {
    
        for(int j=0; j<=4; j++)//四个方向
        {
    
            int x1 = x+dx[j]*i, y1 = y+dy[j]*i;
            if(x1<0 || x1>=n || y1<0 || y1>=n || G[x1][y1]<=G[x][y]) continue;
            ans = max(ans, DP(x1, y1)+G[x][y]);//转移方程
        }
    }
    return ans;
}
int main()
{
    
    while(scanf("%d%d", &n, &k)!=EOF && n!=-1)
    {
    
        for(int i=0; i<n; i++)
        {
    
            for(int j=0; j<n; j++)
            {
    
                scanf("%d", &G[i][j]);
            }
        }
        memset(dp, -1, sizeof(dp));
        printf("%d\n", DP(0, 0));
    }
    return 0;
}
Q - Phalanx

题目链接：Q - Phalanx
参考博文：hdu 2859 （二维dp）

  • 思路：这道题的状态定义和转移方程构造比较巧妙，值得思考。
    • 状态构造：dp[i][j]表示以(i,j)为左下角的对称矩阵的边长。
    • 终态：max(dp[i][j])
    • 状态转移方程：
      • 当i!=0&&dp[i-1][j+1]>i-a时，dp[i][j]=dp[i-1][j+1]+1
      • 当i!=0&&dp[i-1][j+1]<i-a时，dp[i][j]=i-a;（其中a为从当前位置橫纵比较，在纵轴上找，找到的第一个不相等的x的位置,所以i-a就为最大的对称矩阵的长度）
      • 当i==0时，dp[i][j]=1;

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n;
string G[1005];
int dp[1005][1005];//dp[i][j]表示(i, j)为矩阵的左下角

int main()
{
    
    while(cin >> n && n)
    {
    
        getchar();
        for(int i=0; i<n; i++)
            getline(cin, G[i]);
        int ans = 0, a, b, len;
        for(int i=0; i<n; i++)
        {
    
            for(int j=0; j<n; j++)
            {
    
                if(i==0) dp[i][j] = 1;
                else
                {
    
                    a = i, b = j;//a是行，b是列
                    while(G[a][j]==G[i][b])
                    {
    
                        a--, b++;
                        if(a<0 || b>=n) break;
                    }
                    len = i-a;//对称的长度
                    if(len>dp[i-1][j+1]) dp[i][j] = dp[i-1][j+1]+1;
                    else                 dp[i][j] = len;
                }
                if(ans<dp[i][j]) ans = dp[i][j];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
R - Milking Time

题目链接：R - Milking Time

  • 思路：我采用了LIS的状态构造思想。将区间按照结束时间从小到大排列。
    • 状态构造：dp[i]表示以第i个区间为结束的可以获得的最大产量。
    • 终态：max(dp[i])。
    • 状态构造：dp[i] = max(dp[i], dp[j]+T[i].eff)，其中j<i且第j个区间的终止点一定与第i个区间的起始点保持R的距离。
    • 初始化：dp[i] = T[i].eff。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 1005;
int N, M, R;
int dp[MAX];

struct Node
{
    
    int st, ed, eff;
    bool operator < (const Node &A) const
    {
    
        if(ed==A.ed) return st<A.st;
        else         return ed<A.ed;
    }
};
Node T[MAX];

int main()
{
    
    scanf("%d%d%d", &N, &M, &R);
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=M; i++)
    {
    
        scanf("%d%d%d", &T[i].st, &T[i].ed, &T[i].eff);
    }
    sort(T+1, T+M+1);
    for(int i=1; i<=M; i++)
        dp[i] = T[i].eff;
    int ans = dp[1];
    for(int i=2; i<=M; i++)
    {
    
        for(int j=1; j<i; j++)
        {
    
            if(T[j].ed+R<=T[i].st)
                dp[i] = max(dp[i], dp[j]+T[i].eff);
        }
        if(ans<dp[i]) ans = dp[i];
    }
    printf("%d\n", ans);
    return 0;
}
S - Making the Grade

题目链接：S - Making the Grade
参考博文：Making the Grade （线性+优化思维？）

  • 思路：不断的优化，挺难想。
    • 状态构造：dp[i][j]表示将第i个数变成第j小的数的最小代价，变完之后前i个数按序排列。
    • 终态：min(dp[n][j])
    • 状态转移方程：dp[i][j] = min(dp[i-1][k])+abs(a[i]-num[j]);（k<=j）其中a[i]表示第i个数的值，num[j]表示第j小的数的值。
    • 初始化：dp[][] = 0。
      重点是代码的优化，变成了O(n^2)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int MAXN = 2005;
const int INF = 1<<30;//29位报错
int n;
int dp[MAXN],a[MAXN],b[MAXN],num[MAXN];

int get_ans(int a[], int num[])
{
    
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=n; i++)
    {
    
        int Min = INF;
        for(int j=1; j<=n; j++)//得到第i个数变成第j小的数的代价
        {
    
            Min = min(Min, dp[j]);//取第i-1个数变成第k(k<=j)小数的最小代价
            dp[j] = Min + abs(a[i]-num[j]);
        }
    }
    int ans = INF;
    for(int i=1; i<=n; i++) ans = min(ans, dp[i]);
    return ans;
}

int main()
{
    
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
    
        scanf("%d", &a[i]);
        num[i] = a[i];
        b[n-i+1] = a[i];//倒序
    }
    sort(num+1, num+n+1);
    printf("%d\n", min(get_ans(a, num), get_ans(b, num)));
    return 0;
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Accept1234/article/details/100607510

智能推荐

前端开发之vue-grid-layout的使用和实例-程序员宅基地

文章浏览阅读1.1w次，点赞7次，收藏34次。vue-grid-layout的使用、实例、遇到的问题和解决方案_vue-grid-layout

Power Apps-上传附件控件_powerapps点击按钮上传附件-程序员宅基地

文章浏览阅读218次。然后连接一个数据源，就会在下面自动产生一个添加附件的组件。把这个控件复制粘贴到页面里，就可以单独使用来上传了。插入一个“编辑”窗体。_powerapps点击按钮上传附件

C++ 面向对象（Object-Oriented）的特征 & 构造函数& 析构函数_"object(cnofd[\"ofdrender\"])十条"-程序员宅基地

文章浏览阅读264次。(1) Abstraction (抽象)(2) Polymorphism (多态)(3) Inheritance (继承)(4) Encapsulation (封装)_"object(cnofd[\"ofdrender\"])十条"

修改node_modules源码，并保存，使用patch-package打补丁，git提交代码后，所有人可以用到修改后的_修改 node_modules-程序员宅基地

文章浏览阅读133次。删除node_modules，重新npm install看是否成功。在 package.json 文件中的 scripts 中加入。修改你的第三方库的bug等。然后目录会多出一个目录文件。_修改 node_modules

【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure-程序员宅基地

文章浏览阅读883次。【代码】【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure

整理5个优秀的微信小程序开源项目_微信小程序开源模板-程序员宅基地

文章浏览阅读1w次，点赞13次，收藏97次。整理5个优秀的微信小程序开源项目。收集了微信小程序开发过程中会使用到的资料、问题以及第三方组件库。_微信小程序开源模板

随便推点

Centos7最简搭建NFS服务器_centos7 搭建nfs server-程序员宅基地

文章浏览阅读128次。Centos7最简搭建NFS服务器_centos7 搭建nfs server

Springboot整合Mybatis-Plus使用总结(mybatis 坑补充)_mybaitis-plus ruledataobjectattributemapper' and '-程序员宅基地

文章浏览阅读1.2k次，点赞2次，收藏3次。前言mybatis在持久层框架中还是比较火的，一般项目都是基于ssm。虽然mybatis可以直接在xml中通过SQL语句操作数据库，很是灵活。但正其操作都要通过SQL语句进行，就必须写大量的xml文件，很是麻烦。mybatis-plus就很好的解决了这个问题。..._mybaitis-plus ruledataobjectattributemapper' and 'com.picc.rule.management.d

EECE 1080C / Programming for ECESummer 2022 Laboratory 4: Global Functions Practice_eece1080c-程序员宅基地

文章浏览阅读325次。EECE 1080C / Programming for ECESummer 2022Laboratory 4: Global Functions PracticePlagiarism will not be tolerated:Topics covered:function creation and call statements (emphasis on global functions)Objective:To practice program development b_eece1080c

洛谷p4777 【模板】扩展中国剩余定理-程序员宅基地

文章浏览阅读53次。被同机房早就1年前就学过的东西我现在才学，wtcl。设要求的数为\(x\)。设当前处理到第\(k\)个同余式，设\(M = LCM ^ {k - 1} _ {i - 1}\) ，前\(k - 1\)个的通解就是\(x + i * M\)。那么其实第\(k\)个来说，其实就是求一个\(y\)使得\(x + y * M ≡ a_k(mod b_k)\)转化一下就是\(y * M ...

android 退出应用没有走ondestory方法,[Android基础论]为何Activity退出之后，系统没有调用onDestroy方法？...-程序员宅基地

文章浏览阅读1.3k次。首先，问题是如何出现的？晚上复查代码，发现一个activity没有调用自己的ondestroy方法我表示非常的费解，于是我检查了下代码。发现再finish代码之后接了如下代码finish();System.exit(0);//这就是罪魁祸首为什么这样写会出现问题System.exit(0);////看一下函数的原型public static void exit (int code)//Added ..._android 手动杀死app,activity不执行ondestroy

SylixOS快问快答_select函数 导致堆栈溢出 sylixos-程序员宅基地

文章浏览阅读894次。Q: SylixOS 版权是什么形式, 是否分为<开发版税>和<运行时版税>.A: SylixOS 是开源并免费的操作系统, 支持 BSD/GPL 协议(GPL 版本暂未确定). 没有任何的运行时版税. 您可以用她来做任何 您喜欢做的项目. 也可以修改 SylixOS 的源代码, 不需要支付任何费用. 当然笔者希望您可以将使用 SylixOS 开发的项目 (不需要开源)或对 SylixOS 源码的修改及时告知笔者.需要指出: SylixOS 本身仅是笔者用来提升自己水平而开发的_select函数 导致堆栈溢出 sylixos

推荐文章

热门文章

相关标签