1
#include<iostream>
2
#include<cstring>
3
using namespace std;
4
const int N = 210;
5
int a[N];//存数据
6
int f[N];//前缀和
7
int big[N][N];//长度i到j的最大代价
8
int  sm[N][N];//长度i到j的最小代价
9

10
int main()
11
{
12
  int n; cin >> n;
13
  // 读取数据并处理环形
14
  for (int i = 1; i <= n; i++)
15
  {
16
    cin >> a[i];
17
    a[i + n] = a[i]; // 环形处理：复制一遍数组
18
  }
19

20
  int m = n * 2; // 扩展后的数组长度
21
  // 计算前缀和，用于快速求区间和
22
  for (int i = 1; i <= m; i++)
23
  {
24
    f[i] = a[i] + f[i - 1]; // f[i]表示前i堆石子的总重量
25
  }
26

27
  // 初始化DP数组
28
  memset(big, -0x3f, sizeof big); // 最大值初始化为负无穷
29
  memset(sm, 0x3f, sizeof sm);    // 最小值初始化为正无穷
30

31
  // 初始化基础情况：单堆石子合并代价为0
32
  for (int i = 1; i <= m; i++)
33
  {
34
    big[i][i] = 0;
35
    sm[i][i] = 0;
36
  }
37

38
  // 区间DP：枚举区间长度
39
  for (int len = 1; len <= n; len++) // 只需要计算到长度为n的区间
40
  {
41
    for (int left = 1; len + left - 1 <= m; left++) // 枚举区间起点
42
    {
43
      int right = len + left - 1; // 区间终点
44
      // 枚举分割点，将区间分为[left, w]和[w+1, right]
45
      for (int w = left; w < right; w++)
46
      {
47
        // 状态转移方程：
48
        // 合并代价 = 左区间代价 + 右区间代价 + 当前合并的代价(区间石子总数)
49
        big[left][right] = max(big[left][right],
50
                              big[left][w] + big[w + 1][right] + f[right] - f[left - 1]);
51
        sm[left][right] = min(sm[left][right],
52
                              sm[left][w] + sm[w + 1][right] + f[right] - f[left - 1]);
53
      }
54
    }
55
  }
56

57
  // 在环形中找最优解
58
  int maxret = -0x3f3f3f3f; // 最大代价
59
  int minret = 0x3f3f3f3f;  // 最小代价
60
  // 遍历所有可能的起点，区间长度为n
61
  for (int i = 1; i <= n; i++)
62
  {
63
    maxret = max(maxret, big[i][i + n - 1]); // 更新最大代价
64
    minret = min(minret, sm[i][i + n - 1]);  // 更新最小代价
65
  }
66

67
  cout << minret << endl << maxret << endl;
68
  return 0;
69
}

1
#include<iostream>
2
#include<cstring>
3
#include<string>
4
using namespace std;
5
const int N = 5e3+10;
6
bool f[N][N];  // f[l][r]表示交换区间[l,r]的第一个和最后一个字符后
7
               // 是否能使整个字符串的字典序变小
8
string s;
9
int ret;  // 记录符合条件的区间个数
10

11
int main()
12
{
13
    cin>>s;
14
    s=" "+s;  // 让字符串下标从1开始，方便处理
15
    memset(f,0,sizeof f);  // 初始化f数组为false
16

17
    // len表示区间长度，从2开始（因为至少要两个字符才能交换）
18
    for(int len = 2; len < s.size(); len++)
19
    {
20
        // l表示区间左端点
21
        for(int l = 1; l+len-1 < s.size(); l++)
22
        {
23
            int r = l+len-1;  // 区间右端点
24

25
            // 如果区间两端字符相等
26
            if(s[l] == s[r]){
27
                // 能否变小取决于去掉两端后的内部区间
28
                f[l][r] = f[l+1][r-1];
29
                if(f[l][r] == true) ret++;  // 如果能使字符串变小，计数+1
30
            }
31
            // 如果左端字符 > 右端字符
32
            else if(s[l] > s[r]){
33
                f[l][r] = true;  // 交换后左小右大，字符串变小
34
                ret++;  // 计数+1
35
            }
36
            // 如果左端字符 < 右端字符
37
            else if(s[l] < s[r]){
38
                f[l][r] = false;  // 交换后字符串变大，不符合条件
39
                // 不计数
40
            }
41
        }
42
    }
43

44
    cout<<ret<<endl;
45
    return 0;
46
}

1
#include <iostream>
2
#include <queue>
3
using namespace std;
4

5
const int N = 2e5 + 10;
6
int n;
7
int ne[N];    // 存储每个节点指向的下一个节点
8
int in[N];    // 存储每个节点的入度
9
bool st[N];   // 标记数组，用于标记节点是否被访问过或是否在环外
10
int cnt;      // 用于统计环的大小
11

12
// DFS函数：遍历环并统计环的大小
13
void dfs(int a)
14
{
15
    cnt++;        // 环的大小加1
16
    st[a] = true; // 标记当前节点已访问
17
    int b = ne[a]; // 获取当前节点指向的下一个节点
18
    if(!st[b]) dfs(b); // 如果下一个节点未被访问，继续DFS
19
}
20

21
int main()
22
{
23
    cin >> n;
24

25
    // 读取每个节点指向的下一个节点，并计算入度
26
    for(int i = 1; i <= n; i++)
27
    {
28
        cin >> ne[i];
29
        // i -> ne[i]，所以ne[i]的入度加1
30
        in[ne[i]]++;
31
    }
32

33
    // 1. 利用拓扑排序给环以外的点打上标记
34
    queue<int> q;
35
    // 将所有入度为0的节点（不在环中的起点）加入队列
36
    for(int i = 1; i <= n; i++)
37
    {
38
        if(in[i] == 0)
39
            q.push(i);
40
    }
41

42
    // 拓扑排序过程：移除所有不在环中的节点
43
    while(q.size())
44
    {
45
        auto a = q.front(); q.pop();
46
        st[a] = true;  // 标记该节点不在环中
47

48
        int b = ne[a]; // a -> b
49
        in[b]--;       // b的入度减1
50

51
        // 如果b的入度变为0，说明b也不在环中，加入队列
52
        if(in[b] == 0) q.push(b);
53
    }
54

55
    // 2. 利用DFS计算最小环的大小
56
    int ret = n; // 初始化最小环大小为n（最大可能值）
57

58
    // 遍历所有节点，寻找环
59
    for(int i = 1; i <= n; i++)
60
    {
61
        // 如果节点i未被标记（说明在环中）且未被访问过
62
        if(!st[i])
63
        {
64
            cnt = 0;    // 重置计数器
65
            dfs(i);     // 遍历该环
66
            ret = min(ret, cnt); // 更新最小环大小
67
        }
68
    }
69

70
    cout << ret << endl;
71
    return 0;
72
}

1
#include <iostream>
2
#include <queue>
3
#include <vector>
4
#include <cstring>
5
using namespace std;
6

7
typedef pair<int, int> PII;  // 存储边的终点和权重
8
const int N = 1510;
9
int n, m;
10
vector<PII> edges[N];  // 邻接表存储图
11
int in[N];  // 存储每个节点的入度
12
int f[N];   // 存储从节点1到每个节点的最长路径
13

14
int main()
15
{
16
    cin >> n >> m;
17
    // 读入图数据，构建邻接表
18
    for(int i = 1; i <= m; i++)
19
    {
20
        int u, v, w;
21
        cin >> u >> v >> w;
22
        edges[u].push_back({v, w});
23
        in[v]++;  // 终点v的入度加1
24
    }
25

26
    queue<int> q;
27
    // 先处理入度为0，但不是1号结点的结点（这些节点无法从1到达）
28
    for(int i = 2; i <= n; i++)
29
    {
30
        if(in[i] == 0) q.push(i);
31
        f[i] = -1e9;  // 初始化为一个很小的值，表示不可达
32
    }
33

34
    // 拓扑排序预处理：移除那些无法从节点1到达的节点形成的环
35
    while(q.size())
36
    {
37
        auto u = q.front();
38
        q.pop();
39
        for(auto& t : edges[u])
40
        {
41
            int v = t.first;
42
            in[v]--;  // 减少后继节点的入度
43
            if(in[v] == 0) q.push(v);  // 如果入度变为0，加入队列
44
        }
45
    }
46

47
    // 现在处理从节点1开始的路径
48
    q.push(1);
49
    while(q.size())
50
    {
51
        auto u = q.front();
52
        q.pop();
53
        for(auto& t : edges[u])
54
        {
55
            int v = t.first, w = t.second;
56
            // 更新到节点v的最长路径
57
            f[v] = max(f[v], f[u] + w);
58
            in[v]--;  // 减少入度，模拟拓扑排序
59
            if(in[v] == 0) q.push(v);  // 如果入度变为0，加入队列
60
        }
61
    }
62

63
    // 输出结果
64
    //注意memset初始化数组不可为-0x3f3f3f3f,因为实际存到数组里的数和-0x3f3f3f3f不相等
65
    if(f[n] == -1E9)  // 如果节点n不可达
66
        cout << -1 << endl;
67
    else
68
        cout << f[n] << endl;  // 输出从1到n的最长路径
69

70
    return 0;
71
}

1
#include<iostream>
2
#include<vector>
3
#include<queue>
4
#include<cstring>
5
using namespace std;
6

7
const int N = 1600, M = 5E4 + 10;
8
typedef pair<int, int>PII;
9
int n, m;
10
vector<PII>ve[M];  // 邻接表存储图，ve[u]存储从u出发的所有边(终点, 权重)
11
int dist[N];       // 存储从起点1到每个节点的最长距离
12
bool st[N];        // 标记节点是否在队列中
13

14
void spfa()
15
{
16
  queue<int>q;
17
  dist[1] = 0;      // 起点到自身的距离为0
18
  q.push(1);        // 起点入队
19
  st[1] = true;     // 标记起点在队列中
20

21
  while (q.size())   // 队列不为空时循环
22
  {
23
    int u = q.front(); q.pop();  // 取出队首节点
24
    st[u] = false;               // 标记该节点已出队
25

26
    // 遍历u的所有邻接边
27
    for (auto p : ve[u])
28
    {
29
      int v = p.first, w = p.second;  // v是邻接点，w是边权重
30

31
      // 如果通过u到v的路径比当前已知到v的路径更长，则更新
32
      if (dist[u] + w > dist[v])
33
      {
34
        dist[v] = dist[u] + w;  // 更新到v的最长距离
35

36
        // 如果v不在队列中，则加入队列
37
        if (st[v] == false)
38
        {
39
          q.push(v);
40
          st[v] = true;
41
        }
42
      }
43
    }
44
  }
45

46
  // 输出结果：如果终点n不可达则输出-1，否则输出最长距离
47
  if (dist[n] == -1e9)cout << "-1" << endl;
48
  else cout << dist[n] << endl;
49
}
50

51
int main()
52
{
53
  cin >> n >> m;  // 输入节点数n和边数m
54

55
  // 读入所有边信息，构建邻接表
56
  while (m--)
57
  {
58
    int u, v, w;
59
    cin >> u >> v >> w;
60
    ve[u].push_back({ v,w });  // 添加有向边 u->v，权重为w
61
  }
62

63
  // 初始化所有节点到起点的距离为负无穷（表示初始时不可达）
64
  for (int i = 1; i <= n; i++)dist[i] = -1e9;
65

66
  spfa();  // 调用SPFA算法求最长路径
67

68
  return 0;
69
}

1
#include <iostream>
2
using namespace std;
3
typedef long long LL;  // 定义长整型别名，防止数据溢出
4
const int N = 5e5 + 10;  // 定义数组最大大小
5

6
LL n, a, b;    // n-衣服数量，a-自然晾干速度，b-烘干机额外速度
7
LL w[N];       // 存储每件衣服的湿度
8

9
// 检查在x秒内是否能烘干所有衣服
10
bool check(LL x)
11
{
12
    LL cnt = 0;  // 需要烘干机工作的总时间（秒）
13

14
    for(int i = 1; i <= n; i++)
15
    {
16
        // 如果自然晾干就能满足，跳过
17
        if(w[i] <= a * x) continue;
18

19
        // 计算需要烘干机补足的湿度
20
        LL d = w[i] - a * x;
21

22
        // 计算这件衣服需要烘干机工作的时间
23
        // 向上取整：d/b 如果有余数就多需要1秒
24
        cnt = cnt + d / b + (d % b == 0 ? 0 : 1);
25

26
        // 注意：这里应该提前判断，如果cnt已经超过x，可以直接返回false优化性能
27
        // if(cnt > x) return false;
28
    }
29

30
    // 总烘干机时间不超过x秒（因为只有一台机器）
31
    return cnt <= x;
32
}
33

34
int main()
35
{
36
    // 输入数据
37
    cin >> n >> a >> b;
38
    for(int i = 1; i <= n; i++) cin >> w[i];
39

40
    // 二分查找最小时间
41
    LL l = 1, r = 5e5;  // 时间范围：1秒到最大可能时间
42

43
    while(l < r)
44
    {
45
        LL mid = (l + r) / 2;  // 取中间时间
46

47
        if(check(mid))
48
            r = mid;      // mid秒可行，尝试更小的时间
49
        else
50
            l = mid + 1;  // mid秒不可行，需要更多时间
51
    }
52

53
    // 输出最小可行时间
54
    cout << l << endl;
55

56
    return 0;
57
}