C++ 算法题：最小狂暴程度 - 标准输入数据处理 - 常规

C++ 算法题：最小狂暴程度 - 标准输入数据处理

本题要求计算老师狂暴程度的最小值。

输入格式

从标准输入读入数据。

第一行是一个正整数 $n$（$1 \le n \le 1,000$），表示有 $n$ 位同学。
第二行到第 $n+1$ 行，每行两个整数，分别是 $t_i$（$0 \le t_i \le 1,000$）和 $p_i$（$0 \le p_i \le 1,000$）。

输出格式

输出到标准输出。

输出共一行，表示老师狂暴程度 $r$ 的最小值。

样例 #1

样例输入 #1

样例输出 #1

代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1010;
const int INF=0x3f3f3f3f;
int n;
int t[MAXN],p[MAXN];
int dp[MAXN][MAXN];
int main()
{
    scanf('%d',&n);
    for(int i=1;i<=n;i++)
        scanf('%d%d',&t[i],&p[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=1000;j++)
            dp[i][j]=INF;
    dp[1][p[1]]=t[1];
    for(int i=2;i<=n;i++)
        for(int j=0;j<=1000;j++)
            if(j-p[i]>=0)
                dp[i][j]=min(dp[i][j],dp[i-1][j-p[i]]+t[i]);
            dp[i][j]=min(dp[i][j],dp[i-1][j]);
    int ans=INF;
    for(int i=0;i<=1000;i++)
        ans=min(ans,max(i,dp[n][i]));
    printf('%d\n',ans);
    return 0;
}

解题思路

本题可以使用动态规划来解决。设 dp[i][j] 表示前 $i$ 个同学中，总作业分数为 $j$ 时，老师狂暴程度的最小值。

状态转移方程：

 dp[i][j] = min(dp[i][j], dp[i - 1][j - p[i]] + t[i]);

初始化：

 dp[1][p[1]] = t[1];

最终，老师狂暴程度的最小值就是 dp[n][j] 中的最小值。

总结

本题是一个典型的动态规划问题，通过状态转移方程和初始化，可以有效地求解出问题的答案。希望本篇解析能够帮助您更好地理解算法思路和代码实现。