日度归档：4 8 月, 2017

洛谷 [USACO1.5]数字三角形 Number Triangles

发表评论

题号：1216

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<algorithm>
#include<string>
#define INF 2e9
using namespace std;
int n, arr[1005][1005];
int f[1005][1005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + arr[i][j];
        }
    }
    int m = 0;
    for (int i = 1; i <= n; i++){
        if (f[n][i] > m)m = f[n][i];
    }
    cout << m;
}

洛谷 删数问题

发表评论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin >> s;
    cin >> n;
    for (int i = 0; i < s.length(); i++){
        if (s[i]>s[i + 1]&&n>0){
            s.erase(i, 1);
            n--;
            i=-1;//注意这里不是i--;因为有可能不符合顺序的数字出现在前面，需要重新返回头去找！
        }
        if (n == 0)break;
    }
    while (n--){
        s.erase(s.length() - 1, 1);
    }
    while (s[0] == '0')s.erase(s.begin());
    if(!s.empty())cout << s;
    else cout << "0";
}

洛谷 凌乱的yyy

发表评论

题号：1803
首先贴一种我一开始的错误做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct s{
    int start;
    int end;
    bool operator < (s & s1){
        if (end != s1.end)return end < s1.end;
        else return start < s1.start;
    }
}arr[1000005];
bool occupied[1000005];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end;
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++){
        if (!occupied[arr[i].start]){
            for (int j = arr[i].start; j < arr[i].end; j++){
                occupied[j] = true;
            }
            cnt++;
        }
    }
    cout << cnt;
}

这里的21行条件判断是错的。为什么呢？仅判断比赛开头有空闲是不能保证后面的时间有空闲的。那么我写一个正确的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct s{
    int start;
    int end;
    bool operator < (s & s1){
        if (end != s1.end)return end < s1.end;
        else return start > s1.start;
    }
}arr[1000005];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end;
    sort(arr + 1, arr + n + 1);
    int t = 0;
    for (int i = 1; i <= n; i++){
        if (t<=arr[i].start){
            cnt++;
            t = arr[i].end;
        }
    }
    cout << cnt;
}

这次的21行与之前的上一个比赛结束时间进行比较，如果在结束时间后面才能开始这个比赛。
注意：数组是排过序的，以结束时间、开始时间分别升序排序。

洛谷 智力大冲浪

发表评论

题号：1230
一开始想排完序之后直接从前到后由时间1到时间n依次安排，这样做是不对的。
完全可以从一个任务的截止时间开始从后往前安排，哪里有空缺位置就放在那里。
一开始的想法忽略了其他任务也可以放在前面。（说的不太清楚）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
using namespace std;
int m, n;
struct s{
    int t;
    int w;
    bool operator < (s & s1){
        if (w != s1.w)return w>s1.w;
        else return t < s1.t;
    }
}arr[505];
bool occupied[505];
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
        cin >> arr[i].t;
    }
    for (int i = 1; i <= n; i++){
        cin >> arr[i].w;
    }
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++){
        if (!occupied[arr[i].t])occupied[arr[i].t] = true;
        else{
            bool flag = false;
            for (int j = arr[i].t - 1; j >= 1;j--){
                if (!occupied[j]){
                    occupied[j] = true;
                    flag = true;
                    break;
                }
            }
            if (!flag)m -= arr[i].w;
        }
    }
    cout << m;
}