第一题
题目: B - At Most 3 (Judge ver.) (atcoder.jp)
题意:
在数列中找最多3个数，使这几个数的和不超过给定值m，问有多少种选法。
输入格式
第一行是两个整数n和m。
第二行有n个整数。
输出一个整数，代表经过多少秒可以清理垃圾。
数据范围
样例数 1 <= t <=1e4 ，其余均小于100。
输出格式
输出一个整数。
数据范围
1≤ N ≤300
1≤ W ≤106
1≤ Ai ≤106
输入样例：
7 251
202 20 5 1 4 2 100输出样例：
48思路:
- 暴力模拟，但是不能用map，否则会超时。
- 可以用unordered_map或者直接用数组存。
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
const int N = 1e7;
int a[N], p[N];
int n, m;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; ++i)
if (p[a[i]] == 0)
{
p[a[i]] = 1;
if (a[i] <= m)ans++;
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1 + i; j <= n; ++j)
if (p[a[i] + a[j]] == 0)
{
p[a[i] + a[j]] = 1;
if (a[i] + a[j] <= m)ans++;
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = i + 1; j <= n; ++j)
{
for (int k = j + 1; k <= n; ++k)
{
if (p[a[i] + a[j] + a[k]] == 0)
{
p[a[i] + a[j] + a[k]] = 1;
if (a[i] + a[j] + a[k] <= m)ans++;
}
}
}
}
cout << ans;
return 0;
}
第二题
题目: C - Poem Online Judge (atcoder.jp)
题意:
给n个字符串和各自的价值，每个字符串会出现多次，但是只有第一次出现的有意义，可能有多个字符串有相同价值，那么只有第一次出现的字符串有意义。问有意义的字符串最大价值是多少。
输入格式
第一行是一个整数n。
n行，每行是一个字符串和一个整数。
输出格式
一个整数，表示第几个字符串。
数据范围
1≤ N ≤105
字符串的长度在1和10 之间
输入样例：
10
bb 3
ba 1
aa 4
bb 1
ba 5
aa 9
aa 2
ab 6
bb 5
ab 3输出样例：
8思路:
- 水题，直接用map记录一下就好了。
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
const int N = 310;
int a[N];
int n, m;
map<string,int>p;
int main()
{
string s;
cin >> n;
int res = 0,ans=0;
for (int i = 1; i <= n; ++i)
{
cin >> s >> m;
if (p[s] == 0)
{
p[s] = m;
if (m > res)
{
res = m;
ans = i;
}
}
}
cout << ans;
return 0;
}
第四题
题目: E - Takahashi and Animals (atcoder.jp)
题意:
有n个动物，喂养每个动物都有一定的代价，喂养第Ai只动物可以顺便将Ai+1只动物喂饱，如果想要将所有动物喂饱，那么最小代价是多少
输出格式
第一行只有一个整数n。
第二行有n个整数，每个表示喂养第i个动物的代价。
输出格式
一个整数。
数据范围
2≤ N ≤3×10^5
1≤ Ai ≤10^9
输入样例：
20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62输出样例：
426思路:
一眼动态规划，但是做不出来。- 很容易想到，用数组f[i]表示前i个动物都已经喂过的所有方式的集合。然后取集合的最小值即可。
- 这里有个问题，怎么转移？既然我们已经用f[i]表示喂前i个动物的最小代价，那么f[i+1]直接f[i] + a[i+1]不就好了？这是个陷阱，我们不能确定f[i]是否直接喂过Ai，如果Ai是被Ai-1被动喂养的，那么就必须喂养Ai+1；而如果是直接喂养的Ai，就不需要再喂养Ai+1。那么我们可以用f[i] [1]表示直接喂养了Ai，f[i] [0]被动喂养了Ai，那么转移方程就很简单了。
- 还有一个陷阱，如果我们没有直接喂养A1，那么是必须直接喂养An的，而如果直接喂养了A1，那么An喂养与否都可以，最后取值时怎么判断？很简单，跑两遍循环就好了，第一遍不选A1，第二遍选A1。
- 做题时还是不够稳啊，都写出状态转移方程了怎么就是做不对呢！
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define ll long long
const ll N = 300010;
ll a[N];
ll f[N][2];
ll n;
int main()
{
cin >> n;
for (ll i = 1; i <= n; ++i) cin >> a[i];
f[1][0] = 0, f[1][1] = 0x3f3f3f3f;
for (ll i = 2; i <= n; ++i)
{
f[i][0] = f[i - 1][1];
f[i][1] = min(f[i - 1][0], f[i - 1][1]) + a[i];
}
ll ans = f[n][1];//此时必须有n
f[1][0] = 0x3f3f3f3f, f[1][1] = a[1];
for (ll i = 2; i <= n; ++i)
{
f[i][0] = f[i - 1][1];
f[i][1] = min(f[i - 1][0], f[i - 1][1]) + a[i];
}
f[n][0] = min(f[n][0], f[n][1]);//此时n可有可无
cout << min(ans,f[n][0]);
return 0;
}
