/归并排序/
include[HTML_REMOVED]
using namespace std;
const int N = 1000010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r);
{
if (l >= r) return;
int mid = (l + r) / 2;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int k = 0; i = l, j = mid + 1;
while (i <= mid && j < +r)
if (q[i] <= q[j]) tmp[k] = q[i];
else tmp[k] = q[j];
while (i <= mid) tmp[k] = q[i];
while (j <= r) tmp[k] = q[j];
for (int i = l, j = 0; i <= r; i, j) q[i] = tmp[j];
}
int main()
{
scanf(“%d”, &n);
for (int i = 0; i < n; i) scanf(“%d”, &q[i]);
merge_sort(q, 0, n - 1);
for (int i = 0; i < n; i) printf(“%d”, q[i]);
return 0;
}
/单调栈/
include[HTML_REMOVED]
using namespace std;
const int N = 100010;
int n;
int stk[N], tt;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
while (tt & stk[tt] >= x) tt–;
if (tt) cout << stk[tt] << ‘’;
else cout << -1 << ‘’;
stk[++tt] = x;
}
return 0;
}
/滑动窗口/
include[HTML_REMOVED]
using namespace std;
const int N = 1000010;
int n, k;
int a[N], q[N];
int main()
{
scanf(“%d%d”, &n, &k);
for (int i = 0; i < n; i) scanf(“%d”, &a[i]);
int hh = 0, tt = -1;
for (int i = 0; i < n; i)
{
if (hh <= tt && i - k + 1 > q[hh]) hh;
while (hh <= tt && a[q[tt]] >= a[i]) tt–;
q[tt] = i;
if (i >= k - 1) printf(“%d”, a[q[hh]]);
}
puts(“”);
return 0;
}
/并查集/
include[HTML_REMOVED]
using namespace std;
const int N = 100010;
int n, m;
int p[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf(“%d%d”, &n ,& m);
for (int i = 1; i <= n; i++) p[i] = i;
while (m--)
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M') p[find[a]] = find[b];
else
{
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
/堆排序/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int n, m;
int h[N], size;
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
int main()
{
scanf(“%d%d”, &n, &m);
for (int i = 1; i <= n; i++) scanf(“%d”, &h[i]);
size = n;
for (int i = n / 2; i; i–) down(i);
while (m–)
{
printf(“%d”, h[1]);
h[1] = h[size];
size–;
down(1);
}
return 0;
}
/N皇后/
include[HTML_REMOVED]
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i) puts(g[i]);
puts(“”);
return;
}
for(int i=0;i[HTML_REMOVED]> n;
for (int i = 0; i < n; i)
for (int j = 0; j < n; j++)
g[i][j] = ‘.’;
dfs(0);
}
/bfs 走迷宫/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 100010;
int g[N][N];
int d[N][N];
PII q[N * N];
int bfs()
{
int hh = 0; tt = 0;
q[0] = { 0,0 };
memset(d, -1, sizeof d);
d[0][0] = 0;
int dx[x] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
while (hh <= tt)
{
auto t = q[hh];
for (int i = 0; i < 4; i)
{
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0 && d[x][y] == -1)
{
d[x][y] = d[t.first][t.second] + 1;
q[tt] = { x,y };
}
}
}
return d[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i)
for (int j = 0; j < n; j++)
cin >> g[i][j];
cout << bfs() << endl;
}
/拓扑序列/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i)
if (!d[i])
q[tt] = i;
while (hh <= tt)
{
int t = q[hh];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j]–;
if (d[j] == 0) q[tt] = j;
}
}
return tt = n - 1;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i)
{
int a, b;
cin >> a >> b;
add(a, b);
d[b];
}
if (topsort())
{
for (int i = 0; i < n; i++) printf(“%d”, q[i]);
puts(“”);
}
else puts(“-1”);
return 0;
}
/有向图的拓扑序列/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010, M = 100010;
int n, m;
bool st[N];
struct Node
{
int id;
Nodenext
}head[N];
void add(int a, int b)
{
auto p = new Node(b);
p->next = head[a];
head[a] = p;
}
void dfs(int u)
{
st[u] = true;
printf(“%d”, u);
for (auto p = head[u]; p; p->next)
{
int j = p->id;
if (!st[j]) dfs[j];
}
}
/void bfs()
{queue[HTML_REMOVED] q;
q.push(1);
st[1]=true;
while(q.size())
{
auto t=q.front();
q.pop();
printf(“%d”,t);
for(auto p=head[t];p;p->next)
{
j=p->id;
if(!st[j])
{
st[j]=true;
q.push(j);
}
}
}
}*/
int main()
{
scanf("%d%d", &n, &m);
while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
for (int i = 1; i <= n; i++)
if (!st[i])
dfs[i];
return 0;
}
/Dijkstra/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n; i)
{
int t = -1;
for (int j = 1; j <= n; j)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[j] = true;
for (int j = 1; j <= n; j++)
dist[j] = min{ dist[j],dist[j] + g[t][j] };
}
return dist[n];
/*priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> heap;
heap.push({ 0,1 });
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
for (int i = h[t]; i != -1; i = ne[i])
{
j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({ dist[j],j });
}
}
}
if (dist[n] == 0x3f3f3f) return -1;
return dist[n];
}*/
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m--);
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min{ g[a][b],c };
}
int t = dijkstra();
printf("%d\n", t)
return 0;
}
/*Belman ford*/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
const int N = 510, M = 10010;
int n, m, k;
int dist[N], backup[N];
struct Edge
{
int a, b, w;
}edges[M];
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i++)
{
memcpy(backup, dist, sizeof dist);
for (int j = 0; j < m; j++)
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min{ dist[b],backup[a] + w };
}
}
if (dist[n] > 0x3f3f3f / 2) return -1;
return dist[n];
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = { a,b,w };
}
int t = bellman_ford();
if (t == -1) puts("impossible");
else printf("%d\n", t);
return 0;
}
/*floyd*/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int n = 210, INF = 1e9;
int n, m, Q;
int d[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &Q);
memset(d, 0x3f, sizeof d);
for (int i = 1; i <= n; i++) d[i][i] = 0;
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
d[a][b] = min{ d[a][b],c }
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min{ d[i][j],d[i][k] + d[k][j] };
while (Q--)
{
int a, b;
scanf("%d%d", a, b);
int c = d[a][b];
if (c > INF / 2) puts("impossible");
else printf("%d\n", c);
}
return 0;
}
/*prim*/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 510, INF = 0x3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
for (int j = 1; j <= n; j++) dist[j] = min{ dist[j],g[t][j] };
st[t] = true;
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min{ g[a][b],c };
}
int t = prim();
if (t == INF) puts("impossible");
else printf("%d\n", t);
}
/*kruskal*/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 200010;
int n, m;
int p[N];
struct Edge
{
int a, b, w;
bool operator<(const Edge& w) const
{
return w < W.w;
}
}edges[N];
int find(int x)
{
if (p[x] != x) p[x] = find[p[x]];
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i <= m; i++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = { a,b,w };
}
sort(edges, edges + m);
for (int i = 1; i <= n; i++) p[i] = i;
int res = 0, cnt = 0;
for (int i = 0; i < m; i++)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
res += w;
cnt--;
}
}
if (cnt > 1) puts("impossible");
else printf("%d\n", res);
return 0;
}
/*0-1背包*/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if (j > v[i]) f[i][j] = max{ f[i][j],f[i - 1][j - v[i]] + w[i] };
}
cout << f[n][m] << endl;
return 0;
}
/*完全背包问题*/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = i; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k * v[i] <= j; k++)
f[i][j] = max{ f[i][j],f[i - 1][j - v[i] * k] + w[i] * k };
cout << f[n][m] << endl;
return 0;
}
/*线性dp 数字三角形*/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];
int main()
{
scanf("%d", &n)
for (int i = 1; i <= n; i++)
for (int j = 1; j < +i; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i + 1; j++)
f[i][j] = -INF;
f[1][1] = a[1][1];
for (int i = 2; i < +n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = max{ f[i - 1][j - 1] + a[i][j],f[i - 1][j],+a[i][j] };
int res = -INF;
for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}
/*石子合并*/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
for (int i = 1; i <= n; i++) s[i] += s[i - 1];
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 < n; i++)
{
int l = i, r = i + len - 1;
f[l][r] = 1e8;
for (int k = 1; k < r; k++)
f[l][r] = min{ f[l][r],f[l][k] + f[k + 1][r] + s[r] - s[l - 1] };
}
printf("%d\n", f[1][n]);
return 0;
}
/*区间选点*/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator<(const Range& w)const
{
return r < w.r;
}
}ranges[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int l, r;
scanf("%d%d", &l, &r);
ranges[i] = { l,r };
}
sort(ranges, ranges + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i++)
if (ranges[i].l > ed)
{
res++;
ed = ranges[i].r;
}
printf("%d\n", res);
return 0;
}
/*哈夫曼树*/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int main()
{
int n;
scanf("%d", &n);
priority_queue<int, vector<int>, greater<int>> heap;
while (n--)
{
int x;
scanf("%d", &x);
heap.push(x);
}
int res = 0;
while (heap.size() > 1)
{
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
res += a + b;
heap.push(a + b);
}
printf("%d\n", res);
return 0;
}
/*代码随想录*/
/*滑动窗口*/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int p[N];
int n;
int main()
{
int s;
for (int i = 0; i < n; i++) scanf("%d", p[i]);
int result = 1e9;
int sum = 0;
int i = 0;
int sublength = 0;
for (int j = 0; j < n; j++)
{
sum += q[j];
while (sum >= s)
{
sublength = j - i + 1;
result = min{ result,sublength };
sum = sum - q[i];
i++;
}
}
printf("%d", result);
return 0;
}
/*两数之和*/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int n;
int p[N];
int main()
{
int targrt;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", p[i]);
unordered_map<int, int> map;
for (int i = 0; i < n; i++)
{
auto iter = map.find(target - p[i]);
if (iter != map.end())
{
return { iter.second,i };
}
map.insert(p[i], i);
}
}
/*前序非递归遍历*/
void preorder(TreeNode * root)
{
stack<TreeNode*> s;
s.pusn(root);
while (!s.empty())
{
TreeNode* t = s.top();
s.pop();
cout << t->val << '';
if (t->right) s.push(t->right);
if (t->left) s.push(t->left);
}
}
/*中序非递归遍历*/
void inorder(TreeNode * root)
{
stack<TreeNode*> stk;
TreeNode* curr = root;
while (curr || !stk.empty())
{
while (curr)
{
stk.push(curr);
curr = curr->left;
}
curr = stk.top();
stk.pop();
cout << curr->val << "";
curr = curr->right;
}
}
/*插入排序*/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 100010;
int n;
int q[N];
void insert_sort()
{
for (int i = 1; i < n; i++)
{
int t = q[i], j = i;
while (j && q[j - 1] > t)
{
q[j] = q[j - 1];
j--;
}
q[j] = t;
}
}
/折半插入排序/
void binary()
{
for (int i = 1; i < n; i)
{
if (q[i - 1] < q[i]) continue;
int t = q[i];
int l = 0; r = i - 1;
while (l < r)
{
int mid = (l + r) / 2;
if (q[mid] > t) r = mid;
else l = mid + 1;
}
for (int j = i - 1; j >= r; j–)
q[j + 1] = q[j]
q[r] = t;
}
}
void bubble_sort()/冒泡排序/
{
for (int i = 0; i < n - 1; i)
bool has_swap = false;
for (int j = n - 1; j > i; j–)
if (q[j] < q[j - 1])
{
swap(q[j], q[j - 1]);
has_swap = true;
}
if (!has_swap) break;
}
void select_sort()
{
for (int i = 0; i < n; i++)
{
int k = i;
for (j = i + 1; j < n; j++)
if (q[j] < q[k])
k = j;
swap(q[i],q[k])
}
}
}
void quick_sort(int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = (l + r) / 2;
while (i < j)
{
do i++ while (q[i], x);
do j– while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
void down(int u)
{
int t = u;
if (u * 2 <= sz && q[u] < q[2 * u]) t = u * 2;
if (u * 2 + 1 <= sz && q[u] < q[u * 2 + 1]) t = u * 2 + 1;
if (u != t)
{
swap(q[u], q[t]);
down(t);
}
}
void heap_sort()
{
sz = n;
for (int i = n / 2; i; i) down(i);
for (int i = 0; i < n - 1; i)
{
swap(q[1], q[sz]);
sz–;
down(1);
}
}
int main()
{
scanf(“%d”, &n);
for (int i = 0; i < n; i) scanf(“%d”, &q[i]);
insert_sort();
for (int i = 0; i < n; i) printf(“%d\n”, q[i]);
return 0;
}
include[HTML_REMOVED]
using namespace std;
int get(int n)
{
int s = 1;
for (int i = 0; i * i < n; i++)
{
if (n % i == 0)
{
s += i;
if (i * i != n)
s += n / i;
}
}
return s;
}
int main()
{
int n = 1000010;
for (int i = 1; i <= n; i++)
{
int s1 = get(i);
if (s1 > i && s1 < n)
{
int s2 = get(s2);
if (s2 == i)
cout << s1 << ‘’ << s2 << endl;
}
}
return 0;
}
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
bool check(string s, string t)
{
if (s.length() != t.length()) return false;
unordered_map[HTML_REMOVED] cnt;
for (char c : s)
cnt[c]++;
for (char c : t)
cnt[c]–;
for (auto item : cnt)
if (item.second != 0)
return false;
return true;
}
int main()
{
string s, t;
cin >> s >> t;
if (check(s, t))
puts(“true”);
else
puts(“false”);
return 0;
}
/分发饼干/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int g[N], s[N];
int n;
int main()
{
for (int i = 0; i < n; i) scanf(“%d”, &g[i]);
for (int i = 0; i, n; i) scanf(“%d”, &s[i]);
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int index = s.size() - 1;
int result = 0;
for (int i = g.size() - 1; i >= 0; i–)
{
if (index >= 0 && s[index] > g[i])
{
result++;
index–;
}
}
return result;
}
/最大子序和/
int nums[N];
int n;
int main()
{
for (int i = 0; i < n; i) scanf(“&d”, &nums[i]);
int result = 0;
int count = 0;
for (int i = 0; i < nums.size(); i)
{
count += nums[i];
if (count > result) result = count;
if (count <= 0) count = 0;
}
return result;
}
/日期问题/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int months[13] = {
0,31,28,31,30,31,30,31,31,30,31,30,31
};
int is_leap(int year)
{
if (year % 4 == 0 && year % 100 || year % 400 == 0)
return 1;
return 0;
}
int get_days(int y, int m)
{
if (m == 2) return months[m] + is_leap(y);
return months[m];
}
int main()
{
int y, s;
while (cin >> y >> s)
{
int m = 1, d = 1;
s–;
while (s–)
{
if (d > get_days(y, m))
{
d = 1;
if (m > 12)
{
m = 1;
y++
}
}
}
printf(“%04d-%02d-%02d”, y, m, d);
}
return 0;
}
/跳跃游戏/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int nums[N];
int main()
{
int n;
for (int i = 0; i < n; i) scanf(“%d”, &nums[i]);
int cover = 0;
if (nums.size() == 1) return true;
for (int i = 0; i <= cover; i)
{
cover = max(i + nums[i], cover);
if (cover >= nums.size() - 1) return ture;
}
return false;
}
/分发糖果/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int ratings[N], candy[N];
int main()
{
for (int i = 0; i < n; i) candy[i] = 1;
for (int i = 0; i < n; i) scanf(“%d”, &ratings[i]);
for (int i = 1; i < ratings.size(); i++)
{
if (ratings[i] > ratings[i - 1]) candy[i] = candy[i - 1] + 1;
}
for (int i = ratings.size() - 2; i >= 0; i–)
{
if (ratings[i] > ratings[i + 1])
candy[i] = max{ candy[i],candy[i + 1] + 1 };
}
int result = 0;
for (int i = 0; i < candy.size(); i++) result += candy[i];
return result;
}
/加油站/
const int N = 10010;
int gas[N], cost[N];
int main()
{
int cursum = 0;
int totalsum = 0;
int start = 0;
for (int i = 0; i < n; i) scanf(“%d”, &gas[i]);
for (int i = 0; i < n; i) scanf(“%d”, &cost[i]);
for (int i = 0; i < gas.size(); i++)
{
cursum += gas[i] - cost[i];
totalsum += gas[i] - cost[i];
if (cursum < 0)
{
start = i + 1;
cursum = 0;;
}
}
if (totalsum < 0) return -1;
return -1;
}
/爬楼梯/
const int N = 10010;
int dp[N];
int n;
int main()
{
if (n <= 1) return n;
dp[1] = 1;
d[2] = 2;
for (int i = 3; i <= n; i++)
{
dp[i] = d[i - 1] + dp[i - 1];
}
return dp[n];
}
/最小花费爬楼梯/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int dp[N], cost[N];
int n;
int main()
{
for (int i = 0; i < n; i) scanf(“%d”, &cost[i]);
scanf(“%d”, &n);
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i)
{
dp[i] = min{ dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2] };
}
return dp[n];
}
/打家劫舍/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int nums[N];
int dp[N];
int main()
{
int n;
for (int i = 0; i < n; i) scanf(“%d”, nums[i]);
dp[0] = 0;
dp[1] = max{ nums[0],nums[1] };
for (int i = 2; i < n; i)
{
dp[i] = max{ dp[i - 2] + nums[i],dp[i - 1] };
}
return dp[n];
}
/买卖股票/
include[HTML_REMOVED]
using namespace std;
const int N = 10010;
int dp[N], price[N];
int main()
{
int len = price.size();
for (int i = 0; i < len; i) scanf(“%d”, &price[i]);
dp[0][0] = -price[0];
dp[0][1] = 0;
for (int i = 1; i < len; i)
{
dp[i][0] = max{ dp[i - 1][0],-price[i] };
dp[i][1] = max{ dp[i - 1][0],dp[i - 1][1] + price[i] };
}
return dp[len - 1][1];