假网站的域名,恩施做网站,常州网站建设平台,wordpress网站重定向链接#xff1a;Educational DP Contest - AtCoder
A - Frog 1
题意#xff1a;有n个石头#xff0c;从1石头出发#xff0c;每次可以跳一格或者俩格#xff0c;代价为俩个格子间的高度差
思路#xff1a;对于第i个石头#xff0c;可以从石头i-1和i-2得到#xff0c…链接Educational DP Contest - AtCoder
A - Frog 1
题意有n个石头从1石头出发每次可以跳一格或者俩格代价为俩个格子间的高度差
思路对于第i个石头可以从石头i-1和i-2得到比较一下代价即可
f[i]max(f[i-1]abs(h[i]-h[i-1),f[i-2]abs(h[i]-h[i-2])
代码
#include bits/stdc.h
//#define endl \n
#define ll long long
using namespace std;
const ll mod1e97;
const int N1e67;void solve()
{int n;cinn;vectorint a(n);for(int x:a){cinx;}vectorint f(n,1e9);f[0]0;for(int i1;in;i){if(i-10){f[i]min(f[i-1]abs(a[i]-a[i-1]),f[i]);}if(i-20){f[i]min(f[i],min(f[i-1]abs(a[i]-a[i-1]),f[i-2]abs(a[i]-a[i-2])));}}coutf[n-1]endl;}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
B - Frog 2
题意将上一题的跳跃距离改为k
思路枚举i-k到i-1到i的代价就可以了
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e4;
const int N1e57;void solve()
{int n,k;cinnk;vectorint a(n1);for(int i1;in;i) cina[i];vectorint dp(n1,1e9);dp[1]0;//f[0]0;for(int i1;in;i){for(int ji-1;j0(i-j)k;j--){dp[i]min(dp[i],dp[j]abs(a[i]-a[j]));}}coutdp[n]endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
C - Vacation
题意有N天每天可以选择三件事情其中一件事情去做获得该事情当天对应的快乐值不能连续俩天做一样的事情求最大的快乐
思路对于第i天的事情如果做A那就是从前一天做B或者做C转移过来
dp数组开第二维分别对应ABC三件事情 对于BC同理转移
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e4;
const int N1e57;ll f[N][5];
void solve()
{int n;cinn;vectorll a(n1);vectorll b(n1);vectorll c(n1);for(int i1;in;i){cina[i]b[i]c[i];}f[0][1]f[0][2]f[0][3]0;for(int i1;in;i){f[i][1]max(f[i-1][2]a[i],f[i-1][3]a[i]);f[i][2]max(f[i-1][1]b[i],f[i-1][3]b[i]);f[i][3]max(f[i-1][1]c[i],f[i-1][2]c[i]);}coutmax(f[n][1],max(f[n][2],f[n][3]))endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
D - Knapsack 1
题意N件物品每件有一个重量和价值给定一个背包最大容量求最大体积
思路总体积较小的背包问题可以枚举重量dp数组含义为对于重量i的最大价值是多少注意是每件只能拿一件
对于每一种质量i: 可以有
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e4;
const int N1e57;void solve()
{int n,w;cinnw;vectorpairint,ll q(n);for(int i0;in;i){cinq[i].firstq[i].second;}vectorll f(w1,0);for(int i0;in;i){for(int jw;jq[i].first;j--){f[j]max(f[j],f[j-q[i].first]q[i].second);}}//coutf[3]endl;coutf[w]endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
} E - Knapsack 1
题意同上但是w的范围变大了
思路改为枚举价值最后从大到小看价值对于的质量是否超过W
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e4;
const int N1e57;void solve()
{int n,w;cinnw;vectorpairll,int q(n);for(int i0;in;i){cinq[i].firstq[i].second; }vectorll f(N1,1e12);f[0]0;for(int j0;jn;j){for(int iN;iq[j].second;i--){f[i]min(f[i],f[i-q[j].second]q[j].first);}}for(int iN;i0;i--){if(f[i]w){coutiendl;return;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
F - LCS
题意对于俩个字符串找到最大公共字符串
思路dp数组俩维表示a字符串到i的位置b字符串到j的位置的时候的最大匹配
所以有
else
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e4;
const int N3e37;int f[N][N];void solve()
{string a,b;cinab;f[0][0]0;for(int i0;ia.size();i){for(int j0;jb.size();j){if(a[i]b[j]){f[i1][j1]max(f[i1][j1],f[i][j]1);}else{f[i1][j1]max(f[i1][j],f[i][j1]);}}}//coutf[a.size()][b.size()]endl;int ia.size(),jb.size();vectorchar ans;while(i!0j!0){if(a[i-1]b[j-1]){ans.push_back(a[--i]);j--;}else if(f[i-1][j]f[i][j-1]){j--;}else{i--;}}reverse(ans.begin(),ans.end());for(auto it:ans){coutit;}coutendl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
G - Longest Path
题意图上最长路径
思路从一个点出发的时候找他的最长儿子然后从多个点出发都试试
代码
#include bits/stdc.h
//#define endl \n
#define ll long long
using namespace std;
const ll mod1e97;
const int N1e57;vectorint q[N];
int dp[N];
int ans0;
int dfs(int now){//cout1endl;if(dp[now]){return dp[now];}for(auto it:q[now]){dp[now]max(dp[now],dfs(it)1);}return dp[now];
}void solve()
{int n,m;cinnm;for(int i1;im;i){int x,y;cinxy;//if(xy) swap(x,y);q[x].push_back(y);//q[y].push_back(x);}//cout1endl;for(int i1;in;i){ansmax(ans,dfs(i));}coutans;}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
H - Grid 1
题意询问从11到nm的路径数量
思路dp数组俩维表示到ij的时候的路径数量 同时如果(i-1,j)是非法的就不用加(i,j-1)同理如果(i,j)不能走就不用修改了记得取模QAQ
代码
#include bits/stdc.h
//#define endl \n
#define ll long long
using namespace std;
const ll mod1e97;
const int N1e57;char mp[1005][1050];
void solve()
{int n,m;cinnm;for(int i1;in;i){for(int j1;jm;j){cinmp[i][j];}}vectorvectorll f(n1,vectorll(m1,0));f[1][1]1;for(int i1;in;i){for(int j1;jm;j){if(i1j1) continue;if(mp[i][j]#) continue;if(i-11mp[i-1][j]!#){f[i][j]f[i-1][j]%mod;}if(j-11mp[i][j-1]!#){f[i][j]f[i][j-1]%mod;}f[i][j]%mod;}}coutf[n][m]endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
I - Coins
题意有N个硬币丢出后每一有一个概率p共n个p的概率朝上求超过一半的硬币向上的概率
思路dp数组俩维为对于前i个硬币有j个向上 就是当前状态可以由i-1个硬币来这个硬币是朝上或者朝下
注意j-1不能越界
代码
#include bits/stdc.h
//#define endl \n
#define ll long long
using namespace std;
const ll mod1e97;
const int N3e37;double f[N][N];
void solve()
{int n;cinn;vectordouble p(n1);for(int i1;in;i){cinp[i];}f[1][1]p[1];f[1][0](1.0-p[1]);for(int i2;in;i){for(int j0;ji;j){if(j0){f[i][j]f[i-1][j]*(1.0-p[i]);}else{f[i][j]f[i-1][j-1]*p[i]f[i-1][j]*(1.0-p[i]);}}}double ans0;for(int i(n1)/2;in;i){ansf[n][i];}coutsetprecision(12)ansendl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
J - Sushi
题意给定N个盘子每个盘子上面有ai个寿司每次在1到n等概率抽取一个盘子去掉一个寿司如果没有就不用去求去掉全部寿司的期望
思路ai的范围只有1~3我们使用三维dp数组来记录每一种数量的寿司的变化i,j,k表示使用123个寿司的盘子个数
例如使用了三个寿司的盘子那么三个寿司的盘子数量会减少1但是俩个盘子的数量会增加1影响他人的要放在循环的外围还有可以没变化的操作。 其他同理
代码
#include bits/stdc.h
//#define endl \n
#define ll long long
using namespace std;
const ll mod1e97;
const int N3007;
#define all (ijk)double f[N][N][N];
void solve()
{vectorint book(5,0);int n;cinn;for(int i1;in;i){int x;cinx;book[x];}for(int k0;kn;k){for(int j0;jn;j){for(int i0;in;i){if(i||j||k){if(i){f[i][j][k]f[i-1][j][k]*((double)i/all);}if(j){f[i][j][k]f[i1][j-1][k]*((double)j/all);}if(k){f[i][j][k]f[i][j1][k-1]*((double)k/all);}f[i][j][k](double)n/all;}}}}coutsetprecision(12)f[book[1]][book[2]][book[3]]endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
K - Stones
题意一个集合有n个数字轮流拿石头数量为集合中的数字的石头直到有K个石头求谁赢没法拿的人就算输了
思路背包问题的变形dp数组表示数量总和为i的时候的数字然后枚举所有质量所有质量下去看是谁先手后手 代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e4;
const int N3e37;void solve()
{int n,k;cinnk;vectorint v(n1);for(int i1;in;i){cinv[i];}vectorint dp(k1,0);for(int i1;ik;i){for(int j1;jn;j){if(iv[j]){dp[i]|(!dp[i-v[j]]);}}}if(dp[k]){coutFirstendl;}else coutSecondendl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
L - Deque
题意给出一个n个数字的序列俩人轮流从前或者后拿一个数字结果为俩个人分别取到的数字的总和之差先手的要让差尽可能大后手的要让他尽可能小求俩人都用最优策略的结果
思路区间DP可以枚举n个长度的时候取左边还是取右边dp数组表示为在区间[l,r]的时候的结果那么[l,r]区间的结果就是由[l1,r] [l,r-1]得到的 对于后手的考虑成减法就可以了
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e4;
const int N3e37;ll dp[N][N];void solve()
{int n,k;cinn;vectorll a(n1);for(int i1;in;i){cina[i];}memset(dp,0,sizeof(dp));for(int len1;lenn;len){for(int l1,rlen;rn;l,r){if((n-len)%20){dp[l][r]max(dp[l1][r]a[l],dp[l][r-1]a[r]);}else{dp[l][r]min(dp[l1][r]-a[l],dp[l][r-1]-a[r]);}}}coutdp[1][n]endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
M - Candies
题意有N个人要分给他们K个糖果第i个人可以收到0~ai个糖果求有多少种分配方案
思路dp数组表示到第i个人的时候已经分掉了j个糖果那么dp[i][j]的状态就可以从dp[i-1][j-x]
x为0~a[j]
但是光是这样还会超时所以对dp[i-1][j-x]要做一个前缀和处理了
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e97;
const int N1e57;ll dp[105][N];
ll pre[105][N];
void solve()
{int n,k;cinnk;vectorint a(n1);for(int i1;in;i){cina[i];}dp[1][0]pre[1][0]1;for(int i1;ik;i){dp[1][i](ia[1]);pre[1][i]dp[1][i]pre[1][i-1];}for(int i2;in;i){dp[i][0]pre[i][0]1;for(int j1;jk;j){if(ja[i]){dp[i][j]pre[i-1][j]%mod;}else{dp[i][j](pre[i-1][j]-pre[i-1][j-a[i]-1]mod)%mod;}pre[i][j](pre[i][j-1]dp[i][j])%mod;}}coutdp[n][k]endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
N - Slimes
题意石子合并有N块石头每块有一个质量将相邻石头堆合并后代价是俩者的和求最小的代价
思路区间DP从小到大枚举合并的长度然后枚举合并时候的中间点dp数组含义为i开始的长度为len的石头堆合并的代价 代价和可以利用前缀和计算
代码
#include bits/stdc.h
#define ll long long
using namespace std;
const ll mod1e97;
const int N1e57;ll dp[405][405];void solve()
{int n;cinn;vectorll a(n1);vectorll pre(n1);memset(dp,0x3f3f3f,sizeof(dp));for(int i1;in;i){cina[i];pre[i]pre[i-1]a[i];dp[i][1]0;}for(int len2;lenn;len){for(int j1;jn-len1;j){for(int k1;klen;k){dp[j][len]min(dp[j][len],dp[j][k]dp[jk][len-k]pre[jlen-1]-pre[j-1]);//coutdp[j][len]endl;}}}coutdp[1][n]endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
O - Matching
题意有N个男生和N个女生给出一个二维数组代表第i个男生和第j个女生是否匹配求让所有人都匹配的方案数量
思路观察到N的数量很小像是状压DP枚举女生所有状态用01串表示第i个位置是1表示有第i个女生的状态然后和cnt个男生匹配cnt表示该状态中拥有的女生的数量然后枚举每一个i
看mp[cnt][i]是否匹配和这个女生是否存在在这个状态中可以的话进行转移
这个状态可以从没有这个女生且少一个男生的状态转移来利用了滚动数组所以只要dp数组只要记录状态S就行了
S-1i-1)就是从01串中将第i个女生为1去掉
代码
#include bits/stdc.h
//#define endl \n
#define ll long long
using namespace std;
const ll mod1e97;
const int N3007;int mp[25][25];
int f[122];
void solve()
{int n;cinn;for(int i1;in;i){for(int j1;jn;j){cinmp[i][j];}}f[0]1;for(int S1;S1n;S){int cnt__builtin_popcount(S);for(int i1;in;i){if(mp[cnt][i]Si-11){f[S](f[S]f[S-(1i-1)])%mod;}}}coutf[(1n)-1]endl;}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
P - Independent Set
题意给出一棵树要给树上的点染色可以染成白色或者黑色黑色不能连续染求有多少种方案
思路经典树DPdp数组为i的节点是染什么色的0白1红,白色节点的子节点就可以是黑色或者白色黑色节点下面就是白色先遍历子节点然后统计答案 代码
#include bits/stdc.h
//#define endl \n
#define ll long long
using namespace std;
const ll mod1e97;
const int N1e57;vectorint q[N];
ll dp[N][2];void dfs(int now,int fa){dp[now][1]dp[now][0]1;for(auto it:q[now]){if(itfa) continue;dfs(it,now);dp[now][0](dp[now][0]*(dp[it][0]dp[it][1])%mod)%mod;dp[now][1](dp[now][1]*dp[it][0])%mod;}
}void solve()
{int n;cinn;for(int i1;in;i){int x,y;cinxy;q[x].push_back(y);q[y].push_back(x);}dfs(1,0);ll ans(dp[1][0]dp[1][1])%mod;coutansendl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
