Atcoder Educational DP Contest
A - Frog 1
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N;
int f[maxn];
int h[maxn];
int main(){
// debug;
ios;
cin>>N;
for(int i = 1;i<=N;i++) cin>>h[i];
memset(f,0x3f,4*N+10);
f[1] = 0;
for(int i = 1;i<=N;i++){
f[i+1] = min(f[i+1],f[i] + abs(h[i+1] - h[i]));
f[i+2] = min(f[i+2],f[i] + abs(h[i+2] - h[i]));
}
cout<<f[N]<<'\n';
return 0;
}B - Frog 2
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N,K;
int f[maxn];
int h[maxn];
int main(){
// debug;
ios;
cin>>N>>K;
for(int i = 1;i<=N;i++) cin>>h[i];
memset(f,0x3f,4*N+100);
f[1] = 0;
for(int i = 1;i<=N;i++){
for(int j = 1;j<=K;j++){
if(i+j<=N) f[i+j] = min(f[i+j],f[i] + abs(h[i+j] - h[i]));
}
}
cout<<f[N]<<'\n';
return 0;
}
C - Vacation
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N;
int w[maxn][3];
int f[maxn][3];
int main(){
// debug;
ios;
cin>>N;
for(int i = 1;i<=N;i++) cin>>w[i][0]>>w[i][1]>>w[i][2];
f[1][0] = w[1][0],f[1][1] = w[1][1],f[1][2] = w[1][2];
for(int i = 2;i<=N;i++){
for(int j = 0;j<3;j++){
for(int k = 0;k<3;k++){
if(j != k) f[i][j] = max(f[i][j],f[i-1][k] + w[i][j]);
}
}
}
cout<<max(max(f[N][0],f[N][1]),f[N][2])<<'\n';
return 0;
}D - Knapsack 1
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N,W;
int w[maxn],v[maxn];
ll dp[maxn];
int main(){
// debug;
ios;
cin>>N>>W;
for(int i = 1;i<=N;i++) cin>>w[i]>>v[i];
for(int i = 1;i<=N;i++){
for(int j = W;j>=w[i];j--){
dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
}
}
cout<<dp[W]<<'\n';
return 0;
}E - Knapsack 2
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const ll inf = 1e18;
using namespace std;
int N,W;
ll w[maxn],v[maxn];
ll dp[maxn];
int main(){
// debug;
ios;
cin>>N>>W;
for(int i = 1;i<=N;i++) cin>>w[i]>>v[i];
for(int i = 1;i<=N;i++){
for(int j = 100000;j>=v[i];j--){
if(dp[j] == 0){
if(dp[j-v[i]] != 0) dp[j] = dp[j-v[i]] + w[i];
else if(j - v[i] == 0) dp[j] = w[i];
}else{
if(dp[j-v[i]] != 0) dp[j] = min(dp[j],dp[j-v[i]] + w[i]);
else if (j - v[i] == 0) dp[j] = min(dp[j],w[i]);
}
}
}
for(int i = 100000;i>=0;i--){
if(dp[i] != 0 && dp[i] <= W){
cout<<i<<'\n';
return 0;
}
}
cout<<0<<'\n';
return 0;
}F - LCS
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
string s,t;
int f[3030][3030];
pii from[3030][3030];
int lens,lent;
void dfs(int x,int y){
if(x<= 0 || y<=0) return ;
dfs(from[x][y].fs,from[x][y].sc);
cout<<s[x];
}
void upd(int i,int j,int x,int y){
if(s[x] == t[y]) from[i][j] = {x,y};
else from[i][j] = from[x][y];
}
int main(){
// debug;
ios;
cin>>s>>t;
lens = s.length(),lent = t.length();
s = "#" + s; t = "^"+t;
for(int i = 1;i<=lens;i++){
for(int j = 1;j<=lent;j++){
if(s[i] == t[j]) {
f[i][j] = f[i-1][j-1] + 1;
upd(i,j,i-1,j-1);
}else{
f[i][j] = max(f[i-1][j],f[i][j-1]);
if(f[i-1][j] > f[i][j-1]) upd(i,j,i-1,j);
else upd(i,j,i,j-1);
}
}
}
int x = from[lens][lent].fs,y = from[lens][lent].sc;
dfs(x,y);
if(s[lens] == t[lent]) cout<<s[lens];
return 0;
}G - Longest Path
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N,M;
queue<int> q;
int dis[maxn],in[maxn];
int h[maxn],ne[maxn],e[maxn],idx;
void add(int a,int b){
e[++idx] = b,ne[idx] = h[a],h[a] = idx;
}
int solve(){
for(int i = 1;i<=N;i++) if(in[i] == 0) q.push(i);
while(q.size()){
int u = q.front();q.pop();
for(int i = h[u];i;i = ne[i]){
int v = e[i];
dis[v] = max(dis[v],dis[u] + 1);
if(--in[v] == 0){
q.push(v);
}
}
}
int ans = 0;
for(int i = 1;i<=N;i++) ans = max(ans,dis[i]);
return ans;
}
int main(){
// debug;
ios;
cin>>N>>M;
for(int i = 1;i<=M;i++){
int x,y;cin>>x>>y;
add(x,y);
in[y]++;
}
cout<<solve()<<'\n';
return 0;
}
H - Grid 1
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const ll mod = 1000000007;
using namespace std;
int H,W;
char G[1010][1010];
ll f[1010][1010];
ll sovle(){
f[1][1] = 1;
for(int i = 1;i<=H;i++){
for(int j = 1;j<=W;j++){
if(i == 1 && j == 1) continue;
if(G[i][j] == '#') continue;
f[i][j] = (f[i-1][j] + f[i][j-1]) %mod;
}
}
return f[H][W];
}
int main(){
// debug;
ios;
cin>>H>>W;
for(int i = 1;i<=H;i++){
for(int j = 1;j<=W;j++){
cin>>G[i][j];
}
}
cout<<sovle()<<'\n';
return 0;
}
I - Coins
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N;
double p[maxn];
double f[3030][3030];
int main(){
// debug;
ios;
cin>>N;
for(int i = 1;i<=N;i++) cin>>p[i];
f[1][1] = p[1]; f[1][0] = 1-p[1];
for(int i = 2;i<=N;i++){
for(int j = 0;j<=i;j++){
if(j == 0) {
f[i][0] = f[i-1][0] * (1-p[i]);
continue;
}
if (j-1>=0) f[i][j] += f[i-1][j-1] * p[i];
f[i][j] += f[i-1][j] * (1-p[i]);
}
}
double ans = 0;
for(int i = 1;i<=N;i++){
if(i > N-i) ans += f[N][i];
}
cout.precision(10);
cout<<ans<<'\n';
return 0;
}J - Sushi
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N;
int cnt[4];
double dp[333][333][333];
double dfs(int a,int b,int c){
if(a + b + c == 0) return 0.0;
if(dp[a][b][c] > -0.5) return dp[a][b][c];
double res = double(N)/(a+b+c);
if(a) res += dfs(a-1,b,c) * a/(a+b+c);
if(b) res += dfs(a+1,b-1,c) * b/(a+b+c);
if(c) res += dfs(a,b+1,c-1) * c/(a+b+c);
return dp[a][b][c] = res;
}
int main(){
// debug;
ios;
cin>>N;
for(int i = 1;i<=N;i++){
int x;cin>>x;
++cnt[x];
}
for(int i = 0;i<=N;i++)
for(int j = 0;j<=N;j++)
for(int k = 0;k<=N;k++)
dp[i][j][k] = -1;
cout.precision(12);
cout<<dfs(cnt[1],cnt[2],cnt[3])<<'\n';
return 0;
}
K - Stones
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N,K;
int w[maxn],min_w = 1e9;
int f[maxn][2];
bool dfs(int k,int p){
if(k<min_w) return 0;
if(f[k][p] != -1) return f[k][p];
int nx = 1;
for(int i = 1;i<=N;i++) if(k>=w[i]) nx = nx & dfs(k-w[i],p^1);
return f[k][p] = nx ^ 1;
}
int main(){
// debug;
ios;
cin>>N>>K;
for(int i = 1;i<=N;i++) cin>>w[i],min_w = min(min_w,w[i]);
memset(f,-1,sizeof f);
dfs(K,0);
if(f[K][0] == 1) cout<<"First\n";
else cout<<"Second\n";
return 0;
}L - Deque
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N;
ll w[maxn];
ll f[3030][3030]; // = X-Y
ll solve(){
for(int i = 1;i<=N;i++) f[i][i] = w[i];
for(int len = 2;len<=N;len++){
for(int i = 1;i<=N-len+1;i++){
int j = i+len-1;
f[i][j] = max(f[i][j],w[i] - f[i+1][j]);
f[i][j] = max(f[i][j],w[j] - f[i][j-1]);
}
}
return f[1][N];
}
int main(){
// debug;
ios;
cin>>N;
for(int i = 1;i<=N;i++) cin>>w[i];
for(int i = 1;i<=N;i++) for(int j = 1;j<=N;j++) f[i][j] = -1e18;
cout<<solve()<<'\n';
return 0;
}M - Candies
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const ll mod = 1000000007;
using namespace std;
int N,K;
int cnt[maxn];
ll f[111][maxn],pre[maxn];
ll solve(){
for(int i = 0;i<=K;i++) f[1][i] = (i<=cnt[1])? 1:0;
for(int i = 2;i<=N;i++){ // child
memset(pre,0,sizeof pre);
pre[0] = f[i-1][0];
for(int j = 1;j<=K;j++) pre[j] = (f[i-1][j] + pre[j-1]);
for(int j = K;j>=0;j--){ //want to use
if(j-cnt[i]-1 >= 0) f[i][j] = pre[j] - pre[j-cnt[i]-1];
else f[i][j] = pre[j];
f[i][j] %= mod;
}
}
return f[N][K];
}
int main(){
// debug;
ios;
cin>>N>>K;
for(int i = 1;i<=N;i++) cin>>cnt[i];
cout<<solve()<<'\n';
return 0;
}N - Slimes
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N;
ll w[maxn];
ll f[405][405][405];
ll solve(){
memset(f,-1,sizeof f);
for(int i = 1;i<=N;i++) f[1][i][i] = 0;
for(int len = 2;len<=N;len++){
for(int i = 1;i<=N-len+1;i++){
int j = i+len-1;
for(int k = i;k<j;k++){
int lenl = k-i+1,lenr = len-lenl;
if(f[len][i][j] == -1) f[len][i][j] = f[lenl][i][k] + f[lenr][k+1][j] + w[j] - w[i-1];
else f[len][i][j] = min(f[len][i][j],f[lenl][i][k] + f[lenr][k+1][j] + w[j] - w[i-1]);
}
}
}
return f[N][1][N];
}
int main(){
// debug;
ios;
cin>>N;
for(int i = 1;i<=N;i++) cin>>w[i];
for(int i = 1;i<=N;i++) w[i] += w[i-1];
cout<<solve()<<'\n';
return 0;
}O - Matching
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int mod = 1000000007;
using namespace std;
int N;
int G[22][22];
ll f[22][(1<<21)+5];
ll solve(){
for(int j = 0;j<N;j++){
if(G[0][j] == 1) f[0][1<<j] += 1;
}
for(int i = 1;i<N;i++){
for(int j = 0;j<N;j++){
if(G[i][j] == 1){
for(int hs = 0;hs<(1<<N);hs++){
if(!(hs>>j & 1)) f[i][hs | (1<<j)] = (f[i][hs | (1<<j)] + f[i-1][hs])%mod;
}
}
}
}
return f[N-1][(1<<N)-1];
}
int main(){
// debug;
ios;
cin>>N;
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
cin>>G[i][j];
}
}
cout<<solve()<<"\n";
return 0;
}P - Independent Set
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+10;
const int mod = 1000000007;
using namespace std;
int N;
ll f[maxn][2];
int h[maxn],e[maxn*2],ne[maxn*2],idx;
void add(int a,int b){
e[++idx] = b,ne[idx] = h[a],h[a] = idx;
}
void dfs(int u,int fa = -1){
bool isyz = true;
for(int i = h[u]; i ;i = ne[i]){
int v = e[i];
if(v == fa) continue;
isyz = false;
dfs(v,u);
}
if(isyz) f[u][1] = 1,f[u][0] = 1;
else{
ll black = 1,white = 1;
for(int i = h[u]; i; i = ne[i]){
int v = e[i];
if(v == fa) continue;
black *= f[v][1]; black %= mod;
white *= (f[v][1] + f[v][0])%mod; white %= mod;
}
f[u][0] = black,f[u][1] = white;
}
}
int main(){
// debug;
ios;
cin>>N;
for(int i = 1;i<=N-1;i++){
int x,y;cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1);
cout<<(f[1][0] + f[1][1])%mod;
return 0;
}Q - Flowers
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5+10;
using namespace std;
int N;
ll h[maxn],w[maxn],tr[maxn],f[maxn];
int lowbit(int x){
return x&-x;
}
void add(int x,ll v){
for(int i = x;i<=N;i += lowbit(i)) tr[i] = max(tr[i],v);
}
ll query(int r){
ll res = 0;
for(int i = r;i>=1;i -= lowbit(i)) res = max(res,tr[i]);
return res;
}
ll solve(){
for(int i = 1;i<=N;i++){
f[i] = query(h[i]-1) + w[i];
add(h[i],f[i]);
}
ll mx = 0;
for(int i = 1;i<=N;i++) mx = max(mx,f[i]);
return mx;
}
int main(){
// debug;
ios;
cin>>N;
for(int i = 1;i<=N;i++) cin>>h[i];
for(int i = 1;i<=N;i++) cin>>w[i];
cout<<solve()<<'\n';
return 0;
}R - Walk
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int mod = 1e9 + 7;
using namespace std;
ll N,K;
struct node
{
ll M[55][55];
};
node xi,ans;
node mul(const node & A,const node & B){
node ans;
memset(ans.M,0,sizeof ans.M);
for(int i = 1;i<=N;i++){
for(int j = 1;j<=N;j++){
for(int k = 1;k<=N;k++){
ans.M[i][j] += A.M[i][k] * B.M[k][j]%mod; ans.M[i][j] %= mod;
}
}
}
return ans;
}
int main(){
// debug;
ios;
cin>>N>>K;
for(int i = 1;i<=N;i++) for(int j = 1;j<=N;j++) cin>>xi.M[j][i];
for(int i = 1;i<=N;i++) ans.M[i][1] = 1;
while(K){
if(K & 1) ans = mul(xi,ans);
xi = mul(xi,xi);
K >>= 1;
}
ll res = 0;
for(int i = 1;i<=N;i++) res = (res + ans.M[i][1]) %mod;
cout<<res<<'\n';
return 0;
}S - Digit Sum
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e4+10;
const int mod = 1000000007;
using namespace std;
string K;
ll D,len;
ll f[maxn][105];
ll dfs(int pos,int sum,bool limit){
if(!limit && f[pos][sum] != -1) return f[pos][sum];
if(pos == len+1) return f[pos][sum] = sum == 0;
int up = limit ? (K[pos] -'0') : 9;
ll ans = 0;
for(int i = 0;i<=up;i++){
ans += dfs(pos+1,(sum+i)%D,limit && i == up);
ans %= mod;
}
if(!limit) f[pos][sum] = ans;
return ans;
}
int main(){
// debug;
ios;
cin>>K>>D;
len = K.length();
K = '#'+K;
memset(f,-1,sizeof f);
cout<<(dfs(1,0,1) - 1 + mod) %mod<<'\n';
return 0;
}T - Permutation
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int mod = 1e9+7;
using namespace std;
int N;
string s;
ll f[3030][3030];
void solve(){
f[1][1] = 1;
for(int i = 2;i<=N;i++){
if(s[i-1] == '<'){
for(int j = 1;j<=i;j++){
f[i][j] = f[i][j-1] + f[i-1][j-1]; f[i][j] %= mod;
}
}else{
for(int j = i;j>=1;j--){
f[i][j] = f[i][j+1] + f[i-1][j]; f[i][j] %= mod;
}
}
}
ll ans = 0;
for(int i = 1;i<=N;i++) ans = (ans + f[N][i]) %mod;
cout<<ans<<'\n';
}
int main(){
// debug;
ios;
cin>>N;
cin>>s;
s = '#' + s;
solve();
return 0;
}Ryuichi的算法分享 文章被收录于专栏
分享我的一些算法题解，致力于把题解做好，部分题解可能会采用视频的形式来讲解。
美的集团公司福利 133人发布
查看5道真题和解析