题意:给出一个序列a,需要找到一对位置(i, j)(j > i),使得a[j] - a[i]的值尽量大,同时i尽量大并且j尽量小,如果任意a[j] - a[i]都<=0,则输出-1,-1。
题解:从1到n扫一遍序列处理即可,i尽量大用>=,j尽量小用>即可。
代码:
#include <cstdio> #include <iostream> using namespace std; #define maxn (1000000) int a[maxn], prei[maxn]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) { scanf("%d", &a[i]); prei[i] = -1; } int g = -1; for(int i = 0; i < n; i++) { if(g == -1 || a[i] <= a[g]) g = i; if(a[g] < a[i+1]) prei[i+1] = g; } int d = 0, o = -1; for(int i = 1; i < n; i++) if(prei[i] != -1) { if(a[i] - a[prei[i]] > d) { d = a[i] - a[prei[i]]; o = i; } } if(o == -1) cout << -1 << "," << -1 << endl; else cout << prei[o] << "," << o << endl; return 0; }
题意:给出一个序列,玩家需要跟boss进行博弈,玩家先手。每次只能从序列头或尾取一个值加到自己的得分上,玩家和boss都很聪明,求玩家和boss的最终得分。
题解:可以发现总分不是很大,可以记忆化搜索。d[i][j]表示当拿到的序列为a[i, j]时,从中的最高得分。转移方程是d[i][j] = max(a[i] + d[i+1][j], d[i][j-1] + a[j]),向下递归并且记录d[i][j]是否已得到即可(应该算是区间dp?)。
代码:
#include <cstdio> #include <iostream> using namespace std; #define maxn (111) int a[maxn], d[maxn][maxn], vis[maxn][maxn], sum; void dp(int l, int r, int tot) { if(vis[l][r]) return ; if(l == r) { d[l][r] = a[l]; vis[l][r] = 1; return; } dp(l + 1, r, tot - a[l]); dp(l, r - 1, tot - a[r]); d[l][r] = max(tot - d[l + 1][r], tot - d[l][r - 1]); vis[l][r] = 1; } int main() { int N; cin >> N; for(int i = 1; i <= N; i++) { scanf("%d", &a[i]); sum += a[i]; } dp(1, N, sum); cout << d[1][N] << " " << sum - d[1][N] << endl; return 0; }