跑一个完全背包暴力一下答案。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
bool dp[100000005];
int main()
{
ll n, d, e;
sc("%lld%lld%lld", &n, &d, &e);
e *= 5;
dp[0] = true;
for (int i = d; i <= n; i++)
{
if (dp[i - d])
dp[i] = true;
}
for (int i = e; i <= n; i++)
{
if (dp[i - e])
dp[i] = true;
}
ll ans = 1e9;
for (int i = n; i >= 0; i--)
{
if (dp[i])
{
pr("%lld\n", n - i);
return 0;
}
}
} 因为保证a+b>n，所以不会有重复，直接减就可以
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
bool dp[100000005];
int main()
{
int a, b, n;
sc("%d%d%d", &a, &b, &n);
int ans = n + 1;
if (a < n)
{
ans -= n - a;
}
if (b < n)
{
ans -= n - b;
}
pr("%d", ans);
}
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s[200005];
int main()
{
int n;
sc("%d", &n);
sc("%s", s);
if (n & 1)
{
puts("No");
return 0;
}
int l = 0, minn = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '(')
l++;
else
{
l--;
minn = min(minn, l);
}
}
if (l == 0 && minn >= -1)
puts("Yes");
else
puts("No");
} 首先答案最大是2，因为我们可以通过[1,2],[2,1]来使他不能到达终点，考虑两次BFS，第一次求尽量向右走的路径，第二次求尽量向下走的路径，如果走不到终点，输出0，否则，如果两条路径有重合输出1，否则输出2。
#include<bits/stdc++.h>
#define Pair pair<int,int>
#define sc scanf
#define pr printf
using namespace std;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
char s[n + 1][m + 1];
for (int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
int sum[n + 1][m + 1];
bool vis[n + 1][m + 1];
memset(sum, 0, sizeof(sum));
Pair fa[n + 1][m + 1];
vector<Pair>v;
//bfs1
queue<Pair>q1;
int dir1[2][2] = { 0,1,1,0 };
q1.push(Pair{ 1,1 });
memset(vis, false, sizeof(vis));
vis[1][1] = true;
while (!q1.empty())
{
Pair t = q1.front();
q1.pop();
for (int k = 0; k < 2; k++)
{
int tx = t.first + dir1[k][0];
int ty = t.second + dir1[k][1];
if (tx<1 || tx>n || ty<1 || ty>m)continue;
if (vis[tx][ty] == false && s[tx][ty] == '.')
{
vis[tx][ty] = true;
q1.push(Pair{ tx,ty });
fa[tx][ty] = t;
}
if (tx == n && ty == m)
{
t = Pair{ tx,ty };
t = fa[t.first][t.second];
while (t.first != 1 || t.second != 1)
{
v.push_back(t);
t = fa[t.first][t.second];
}
goto qwe1;
}
}
}
qwe1:;
//bfs2
queue<Pair>q2;
int dir2[2][2] = { 1,0,0,1 };
q2.push(Pair{ 1,1 });
memset(vis, 0, sizeof(vis));
vis[1][1] = true;
while (!q2.empty())
{
Pair t = q2.front();
q2.pop();
for (int k = 0; k < 2; k++)
{
int tx = t.first + dir2[k][0];
int ty = t.second + dir2[k][1];
if (tx<1 || tx>n || ty<1 || ty>m)continue;
if (vis[tx][ty] == false && s[tx][ty] == '.')
{
vis[tx][ty] = true;
q2.push(Pair{ tx,ty });
fa[tx][ty] = t;
}
if (tx == n && ty == m)
{
t = Pair{ tx,ty };
t = fa[t.first][t.second];
while (t.first != 1 || t.second != 1)
{
v.push_back(t);
t = fa[t.first][t.second];
}
goto qwe2;
}
}
}
qwe2:;
sort(v.begin(), v.end());
if (v.size() == 0)
pr("0\n");
else if (unique(v.begin(), v.end()) != v.end())
pr("1\n");
else
pr("2\n");
}
/*
3 4
....
.#.#
..#.
*/ E - Petya and Construction Set
给出n个长度，第i个长度点2*i-1与2*i的距离，求一颗满足上述条件的2*n个结点的数（保证答案一定存在
1、构造，考虑将两个点看成一条链，然后从大到小排序
2、我们以最长链作为主链，那么只要我们把主链填满了，剩下的所有链都可以加在主链上。
3、考虑如何填满主链，从左向右遍历找到一个主链没有放结点的位置，然后将当前最长的链的一头放在这个节点上，然后向后延伸，那么他的另一个结点有三种情况
a、主链上放不下，那么他一定要放在主链的尾部的下一个结点，即将主链延长（因为长度是有序的
b、主链上能放下，并且这个位置没有放结点，那么我们考虑将这个点放在主链上。
c、主链上能放下，但这个位置有别的结点，那么我们考虑让这个点和这个位置的前一个位置的点连接。
4、主链构造满之后，剩下的所有链，第一个点连主链的第一个点，然后根据长度计算下一个点的位置就可以。
5、在 3c 构造的时候，注意 这个位置的前一个位置 不一定存在点，所以我们是让这个点和前一个位置直接连接，最后输出的时候，在根据位置来找输出的值。
#include <bits/stdc++.h>
#define Pair pair<int,int>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e6 + 10;
int n, len, path1[MAXN], path2[MAXN], pos[MAXN];
//path1表示主链上的点
//path2表示与主链上的某个点相接
//pos表示与非主链上的点相接
Pair in[MAXN];
int u = 2;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &in[i].second);
in[i].first = i;
}
sort(in + 1, in + 1 + n, [](Pair q, Pair w) {
return q.second > w.second;
});
path1[1] = in[1].first * 2;
len = in[1].second + 1;
path1[len] = in[1].first * 2 - 1;
//构造主链
for (int i = 2; i <= len; ++i)
{
if (path1[i] != 0)
continue;
path1[i] = in[u].first * 2;
int second = in[u].second + i;
if (second > len)
{
path1[len + 1] = in[u].first * 2 - 1;
++len;
}
else
{
if (path1[second] != 0)
pos[in[u].first * 2 - 1] = second - 1;
else
path1[second] = in[u].first * 2 - 1;
}
++u;
}
//加边
while (u <= n)
{
path2[in[u].first * 2] = path1[1];
if (in[u].second == 1)
path2[in[u].first * 2 - 1] = in[u].first * 2;
else
path2[in[u].first * 2 - 1] = path1[in[u].second - 1];
++u;
}
//output
for (int i = len; i >= 2; i--)
printf("%d %d\n", path1[i], path1[i - 1]);
for (int i = 1; i <= 2 * n; ++i)
{
if (path2[i])
printf("%d %d\n", i, path2[i]);
if (pos[i])
printf("%d %d\n", i, path1[pos[i]]);
}
}
京公网安备 11010502036488号