• 刷题记录(NC16664 [NOIP2004]合唱队形,NC235954 滑雪,NC235948 最大子串和,NC235624 牛可乐和最长公共子序列)


    NC16664 [NOIP2004]合唱队形

    题目链接

    关键点:

    1、题目要求求出连续的最长上升子序列+最长下降子序列

    2、我们求出从左到右的每个点最长上升子序列,从右到左每个点的最长上升子序列

    3、答案即为看每个位置的最长上升子序列长度+最长下降子序列长度的最大值

    完整代码:

    1. # include
    2. using namespace std;
    3. int n, ans;
    4. int a[110];
    5. int dpr[110], dpl[110];
    6. int main()
    7. {
    8. cin>>n;
    9. for (int i=1; i<=n; i++)
    10. {
    11. cin>>a[i];
    12. dpr[i] = 1;
    13. dpl[i] = 1;
    14. }
    15. for (int i=1; i<=n; i++)
    16. {
    17. for (int j=1; j
    18. {
    19. if (a[i]>a[j])
    20. dpl[i] = max(dpl[i], dpl[j]+1);
    21. }
    22. }
    23. for (int i=n; i>=1; i--)
    24. {
    25. for (int j=n; j>i; j--)
    26. {
    27. if (a[i]>a[j])
    28. dpr[i] = max(dpr[i], dpr[j]+1);
    29. }
    30. }
    31. for (int i=1; i<=n; i++)
    32. {
    33. // cout<
    34. ans = max(ans, dpl[i]+dpr[i]-1);
    35. }
    36. cout<
    37. return 0;
    38. }

    NC235954 滑雪

    题目链接

    关键点:

    1、对于每一个点的下滑长度,为其四周下滑长度+1的值取最大值

    2、最好采用记忆化搜索,如果采用直接递推,不能按照数组的顺序去推,一个数的四周不一定在之前已经算出来。采用记忆化搜索,遇到没算出来的值,可以先调用函数先算出

    完整代码:

    1. # include
    2. using namespace std;
    3. int n, m;
    4. int g[110][110];
    5. int dp[110][110];
    6. int X[5] = {1, -1, 0, 0};
    7. int Y[5] = {0, 0, 1, -1};
    8. int find(int x, int y)
    9. {
    10. if (dp[x][y])
    11. return dp[x][y];
    12. dp[x][y] = 1;
    13. for (int i=0; i<4; i++)
    14. {
    15. int x1 = X[i] + x;
    16. int y1 = Y[i] + y;
    17. if (x1<=0||y1<=0||x1>n||y1>m)
    18. continue;
    19. if (g[x][y] > g[x1][y1])
    20. dp[x][y] = max(dp[x][y], find(x1, y1)+1);
    21. }
    22. return dp[x][y];
    23. }
    24. int main()
    25. {
    26. cin>>n>>m;
    27. for (int i=1; i<=n; i++)
    28. {
    29. for (int j=1; j<=m; j++)
    30. cin>>g[i][j];
    31. }
    32. int ans = 0;
    33. for (int i=1; i<=n; i++)
    34. {
    35. for (int j=1; j<=m; j++)
    36. {
    37. // cout<
    38. ans = max(ans, find(i, j));
    39. }
    40. }
    41. cout<
    42. return 0;
    43. }

    NC235948 最大子串和

    题目链接

    关键点:

    1、对于一个数组,对于每一位,我们都算出选择该数的最大值,那么就有就和是否选择之前的数进行比较

    dp[i] = max(dp[i-1]+a[i], a[i]);表示选择当前数的最大值(一定选择当前数,看是否选择之前的数)

    完整代码:

    1. # include
    2. using namespace std;
    3. typedef long long ll;
    4. int n;
    5. ll a[1000000+10];
    6. ll dp[1000000+10];
    7. ll ans;
    8. int main()
    9. {
    10. cin>>n;
    11. for (int i=1; i<=n; i++)
    12. cin>>a[i];
    13. for (int i=1; i<=n; i++)
    14. {
    15. dp[i] = max(a[i]+dp[i-1], a[i]);
    16. }
    17. for (int i=1; i<=n; i++)
    18. {
    19. ans = max(ans, dp[i]);
    20. }
    21. cout<
    22. return 0;
    23. }

    NC235624 牛可乐和最长公共子序列

    题目链接

    关键点:

    1、注意该题有多组数据!

    2、对于两个序列,我们取两个序列的结尾来推

    3、dp[i][j];表示第一个序列到i,但不包括i,第二个序列到j ,但不包括j

    那么比较i前一个字母和j的前一个字母看是否相同,相同则为之前的+1,即

    dp[i][j] = dp[i-1][j-1]+1;

    该式子也表明了我们为什么不将动态转移方程设为包括i, j,如果从0开始遍历,数组下标会越界

    4、如果i-1字母和j-1不相同,那么就在两个串分别减少一个长度中取最大值

    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);

    5、因为该方程是从头一点点遍历到尾,所以最终答案即为dp[s1.size()][s2.size()];

    完整代码:

    1. # include
    2. using namespace std;
    3. string s1, s2;
    4. int dp[5010][5010];
    5. int main()
    6. {
    7. while(cin>>s1>>s2)
    8. {
    9. // memset(dp, 0, sizeof(dp));
    10. for (int i=1; i<=s1.size(); i++)
    11. {
    12. for (int j=1; j<=s2.size(); j++)
    13. {
    14. if (s1[i-1] == s2[j-1])
    15. dp[i][j] = dp[i-1][j-1]+1;
    16. else
    17. dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    18. }
    19. }
    20. cout<size()][s2.size()]<
    21. }
    22. return 0;
    23. }

  • 相关阅读:
    Transformer与强化学习结合提升物联网智能决策
    YOLOv7 Backbone| 原文源码详解
    PAT 乙级1085 PAT单位排行
    .NET Core Hangfire任务计划
    项目管理到底管的是什么?
    【在SpringBoot项目中使用Validation框架检查数据格式】
    景联文科技提供4D-BEV标注工具:提升自动驾驶感知能力的精准数据支持
    SpringMVC之注解RequestMapping
    C#中的DateTime类
    Docker环境应用迁移
  • 原文地址:https://blog.csdn.net/m0_60531106/article/details/126612479