SCIST
基本：基礎
No judge - 爬樓梯問題
有一個 N 階的樓梯，你站在第 0 階上，每一步只能爬 1 階或 2 階，且只能向上爬，不能往下走，求有多少種不同方法可以抵達第 N 階。
top down
#include<bits/stdc++.h>
using namespace std;
int n,dp[10005];
bool used[10005]={0};
int dfs(int n){
if(used[n]) return dp[n];
used[n]=1;
return dp[n] = dfs(n-1)+dfs(n-2);
}
int main(){
cin>>n;
used[0]=1,used[1]=1,dp[0]=1,dp[1]=1;
cout<<dfs(n)<<"\n";
}
bottom up
#include<bits/stdc++.h>
using namespace std;
int n,dp[10005];
int main(){
cin>>n;
dp[0]=1,dp[1]=1;
for(int i=2 ; i<=n ; i++){
dp[i] = dp[i-1] + dp[i-2];
}
cout<<dp[n];
}
No judge - 爬樓梯問題．改
有一個 N 階的樓梯，你站在第 0 階上，每一步只能爬 1 階或 2 階，且只能向上爬，不能往下走，抵達第 i 階時要付 Ci 的過路費，求最佳策略下，抵達第 N 階上的最小過路費總和。
top down
#include<bits/stdc++.h>
using namespace std;
int n,dp[10005],c[10005];
bool used[10005];
int dfs(int n){
if(used[n]) return dp[n];
used[n]=1;
return dp[n] = min(dfs(n-1),dfs(n-2))+c[n];
}
int main(){
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>c[i];
used[0]=1,used[1]=1,dp[1]=c[1],dp[0]=0;
cout<<dfs(n)<<"\n";
}
bottom up
#include<bits/stdc++.h>
using namespace std;
int n,dp[10005],c[10005];
int main(){
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>c[i];
dp[0]=0,dp[1]=c[1];
for(int i=2 ; i<=n ; i++){
dp[i] = min(dp[i-1] , dp[i-2]) + c[i];
}
cout<<dp[n];
}
No judge - 極．爬樓梯問題
有一個 N 階的樓梯，你站在第 0 階上，每一步只能爬 1、2 或 3 階，嚴禁連續兩步都爬同樣多階，且只能向上爬，不能往下走，求有多少種不同方法可以抵達第 N 階。
bottom up
#include<bits/stdc++.h>
using namespace std;
int n,dp[10005][4];
int main(){
cin>>n;
dp[0][1]=1,dp[0][2]=0,dp[0][3]=0;
dp[1][1]=1,dp[1][2]=0,dp[1][3]=0;
dp[2][1]=0,dp[2][2]=1,dp[2][3]=0;
for(int i=3 ; i<=n ; i++){
dp[i][1] = dp[i-1][2] + dp[i-1][3];
dp[i][2] = dp[i-2][1] + dp[i-2][3];
dp[i][3] = dp[i-3][2] + dp[i-3][1];
}
cout<<dp[n][1]+dp[n][2]+dp[n][3];
}
No judge - 爬樓梯問題．改二
有一個 N 階的樓梯，你站在第 0 階上，每一步只能爬 1 階或 2 階，且只能向上爬，不能往下走，抵達第 i 階時要付 Ci 的過路費，但是你兄弟會幫你出掉大部份的過路費，你只要付最終過路費的個數即可。求最佳策略下，抵達第 N 階所需付的最小金額（兄弟幫付的不計）。
bottom up
#include<bits/stdc++.h>
using namespace std;
int c[10005];
bool dp[10005][12];
int main(){
int n;
cin>>n;
for(int i=1 ; i<=n ; i++){
cin>>c[i];
c[i]%=10;
}
for(int i=0 ; i<=9 ; i++){
dp[0][i]=0;
dp[1][i]=0;
dp[2][i]=0;
}
dp[0][0]=1;
dp[1][c[1]%10]=1;
dp[2][(c[1]+c[2])%10]=1;
dp[2][c[2]%10]=1;
for(int i=3 ; i<=n ; i++){
for(int j=0 ; j<=9 ; j++){
dp[i][j]=dp[i-1][(j+10-c[i])%10] || dp[i-2][(j+10-c[i])%10];
}
}
for(int i=0 ; i<=9 ; i++){
if(dp[n][i]==1){
cout<<i<<"\n";
break;
}
}
}
TOJ 470 - 公假無雙
bottom up
#include<bits/stdc++.h>
using namespace std;
int e[1000005];
int dp[1000005][2];
int main(){
int n;
while(cin>>n){
for(int i=1 ; i<=n ; i++) cin>>e[i];
dp[0][0]=0;
dp[1][1]=e[1] , dp[1][0]=0;
for(int i=2 ; i<=n ; i++){
dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
dp[i][1]=dp[i-1][0]+e[i];
}
cout<<max(dp[n][0],dp[n][1])<<"\n";
}
}
AtCoder dp_a - Frog 1
bottom up
#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int h[100005];
int main(){
int n;
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>h[i];
dp[1]=0;
dp[2]=abs(h[1]-h[2]);
for(int i=3 ; i<=n ; i++){
dp[i]=min( dp[i-1]+abs(h[i]-h[i-1]) , dp[i-2]+abs(h[i]-h[i-2]));
}
cout<<dp[n];
}
AtCoder dp_b - Frog 2
bottom up
#include<bits/stdc++.h>
using namespace std;
int h[100005];
int dp[100005]; //chose i
int main(){
int n,k;
cin>>n>>k;
for(int i=1 ; i<=n ; i++) cin>>h[i];
for(int i=1 ; i<=k+1 ; i++){
dp[i]=abs(h[1]-h[i]);
}
for(int i=k+2 ; i<=n ; i++){
dp[i] = 1000000001;
for(int j=i-k ; j<i ; j++){
dp[i] = min(dp[i],dp[j] + abs(h[i]-h[j]));
}
}
cout<<dp[n]<<"\n";
}
AtCoder dp_c - Vacation
bottom up
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
int c[100005];
int dp[100005][3];
int main(){
int n;
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>a[i]>>b[i]>>c[i];
dp[1][0] = a[1]; //a
dp[1][1] = b[1]; //b
dp[1][2] = c[1]; //c
for(int i=2 ; i<=n ; i++){
dp[i][0] = a[i] + max(dp[i-1][1],dp[i-1][2]);
dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2]);
dp[i][2] = c[i] + max(dp[i-1][0],dp[i-1][1]);
}
cout<<max(max(dp[n][0],dp[n][1]),dp[n][2])<<"\n";
}
TOJ 540 - 鐵人三項
bottom up
#include<bits/stdc++.h>
using namespace std;
long long t[200005][3];
long long dp[200005][3];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin>>n;
for(int i=1 ; i<=n ; i++){
cin>>t[i][0]>>t[i][1]>>t[i][2];
}
dp[1][0] = t[1][0];
dp[2][0] = dp[1][0] + t[2][0];
dp[2][1] = t[1][0] + t[2][1];
dp[3][0] = dp[2][0] + t[3][0];
dp[3][1] = min(dp[2][0],dp[2][1]) + t[3][1];
dp[3][2] = dp[2][1] + t[3][2];
for(int i=4 ; i<=n ; i++){
dp[i][0] = dp[i-1][0] + t[i][0];
dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + t[i][1];
dp[i][2] = min(dp[i-1][1],dp[i-1][2]) + t[i][2];
}
cout<<dp[n][2]<<"\n";
}
基本：有點變化
UVa 369
bottom up
#include<bits/stdc++.h>
using namespace std;
unsigned long long dp[105][105];
int main(){
int n,m;
while(cin>>n>>m && (n|m)){
dp[0][0] = 1LL;
for(int i=1 ; i<=n ; i++){
dp[i][0] = 1LL;
for(int j=1 ; j<=i ; j++){
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
}
}
cout<<n<<" things taken "<<m<<" at a time is "<<dp[n][m]<<" exactly.\n";
}
}
UVa 10198
bottom up
#include <bits/stdc++.h>
using namespace std;
#define MAXN 9999
#define MAXSIZE 1010
#define DLEN 4
class BigNum
{
private:
int a[500];
int len;
public:
BigNum(){len=1;memset(a,0,sizeof(a));}
BigNum(const int);
BigNum(const char*);
BigNum(const BigNum &);
BigNum &operator=(const BigNum &);
friend istream& operator>>(istream&,BigNum&);
friend ostream& operator<<(ostream&,BigNum&);
BigNum operator+(const BigNum &)const;
};
BigNum::BigNum(const int b)
{
int c,d=b;
len=0;
memset(a,0,sizeof(a));
while(d>MAXN)
{
c=d-(d/(MAXN+1))*(MAXN+1);
d=d/(MAXN+1);
a[len++]=c;
}
a[len++]=d;
}
BigNum::BigNum(const char *s)
{
int t,k,index,L,i;
memset(a,0,sizeof(a));
L=strlen(s);
len=L/DLEN;
if(L%DLEN)len++;
index=0;
for(i=L-1;i>=0;i-=DLEN)
{
t=0;
k=i-DLEN+1;
if(k<0)k=0;
for(int j=k;j<=i;j++)
t=t*10+s[j]-'0';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum &T):len(T.len)
{
int i;
memset(a,0,sizeof(a));
for(i=0;i<len;i++)
a[i]=T.a[i];
}
BigNum & BigNum::operator=(const BigNum &n)
{
int i;
len=n.len;
memset(a,0,sizeof(a));
for(i=0;i<len;i++)
a[i]=n.a[i];
return *this;
}
istream& operator>>(istream &in,BigNum &b)
{
char ch[MAXSIZE*4];
int i=-1;
in>>ch;
int L=strlen(ch);
int count=0,sum=0;
for(i=L-1;i>=0;)
{
sum=0;
int t=1;
for(int j=0;j<4&&i>=0;j++,i--,t*=10)
{
sum+=(ch[i]-'0')*t;
}
b.a[count]=sum;
count++;
}
b.len=count++;
return in;
}
ostream& operator<<(ostream& out,BigNum& b)
{
int i;
cout<<b.a[b.len-1];
for(i=b.len-2;i>=0;i--)
{
printf("%04d",b.a[i]);
}
return out;
}
BigNum BigNum::operator+(const BigNum &T)const
{
BigNum t(*this);
int i,big;
big=T.len>len?T.len:len;
for(i=0;i<big;i++)
{
t.a[i]+=T.a[i];
if(t.a[i]>MAXN)
{
t.a[i+1]++;
t.a[i]-=MAXN+1;
}
}
if(t.a[big]!=0)
t.len=big+1;
else t.len=big;
return t;
}
BigNum dp[1005];
int main(){
int n;
while(cin>>n){
dp[0]=1;
for(int i=1 ; i<=n ; i++){
dp[i]=dp[i-1]+dp[i-1];
if(i-2>=0) dp[i] = dp[i] + dp[i-2];
if(i-3>=0) dp[i] = dp[i] + dp[i-3];
}
cout<<dp[n]<<"\n";
}
return 0;
}
經典：最大連續和
UVa 10684 - The jackpot
bottom up
#include<bits/stdc++.h>
using namespace std;
int dp[10005];
int s[10005];
int main(){
int n;
while(cin>>n && n){
for(int i=1 ; i<=n ; i++) cin>>s[i];
dp[1] = s[1];
int mx = dp[1];
for(int i=2 ; i<=n ; i++){
dp[i] = s[i] + max(0,dp[i-1]);
mx = max(mx,dp[i]);
}
if(mx<=0) cout<<"Losing streak.\n";
else cout<<"The maximum winning streak is "<<mx<<".\n";
}
}
經典：最長共同子序列（LCS）
UVa 10405
bottom up
#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main(){
string a,b;
while(cin>>a>>b){
int la = a.size(),lb = b.size();
for(int i=0 ; i<=la ; i++) dp[i][0] = 0;
for(int j=0 ; j<=lb ; j++) dp[0][j] = 0;
for(int i=1 ; i<=la ; i++){
for(int j=1 ; j<=lb ; j++){
if(a[i-1] == b[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
else{
dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
}
}
}
cout<<dp[la][lb]<<"\n";
}
}
AP325
1D0D
P-6-1. 小朋友上樓梯最小成本
bottom up
#include<bits/stdc++.h>
using namespace std;
int h[100005];
int dp[100005];
int main(){
int n;
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>h[i];
dp[1] = h[1];
dp[2] = h[2];
for(int i=3 ; i<=n ; i++){
dp[i] = min(dp[i-1],dp[i-2]) + h[i];
}
cout<<dp[n]<<"\n";
}
P-6-2. 不連續的表演酬勞
bottom up
#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int cost[100005];
int main(){
int n;
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>cost[i];
dp[1] = cost[1],dp[2]=max(cost[1],cost[2]);
for(int i=3 ; i<=n ; i++){
dp[i] = max(cost[i] + dp[i-2] , dp[i-1]);
}
cout<<dp[n]<<"\n";
}
P-6-3. 最小監控鄰居的成本
bottom up
#include<bits/stdc++.h>
using namespace std;
int cost[100005];
int dp[100005]; //chose i
int main(){
int n;
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>cost[i];
dp[0] = dp[1] = cost[1];
dp[2] = cost[2];
dp[3] = cost[3] + min(cost[1],cost[2]);
for(int i=4 ; i<=n ; i++){
dp[i] = min(min(dp[i-3] , dp[i-2]),dp[i-1]) + cost[i];
}
cout<<min(dp[n],dp[n-1])<<"\n";
}
Q-6-4. 闖關二選一
bottom up
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
int dp[100005][2];
int main(){
int n,t;
cin>>n>>t;
for(int i=1 ; i<=n ; i++) cin>>a[i]>>b[i];
dp[1][0] = abs(a[1]-t);
dp[1][1] = abs(b[1]-t);
for(int i=2 ; i<=n ; i++){
dp[i][0] = min(dp[i-1][0] + abs(a[i]-a[i-1]), dp[i-1][1] + abs(a[i]-b[i-1]));
dp[i][1] = min(dp[i-1][0] + abs(b[i]-a[i-1]), dp[i-1][1] + abs(b[i]-b[i-1]));
}
cout<<min(dp[n][0],dp[n][1])<<"\n";
}
2D0D
P-6-6. 方格棋盤路線
bottom up
#include<bits/stdc++.h>
using namespace std;
int s[205][205];
int dp[205][205];
int main(){
int m,n;
cin>>m>>n;
for(int i=1 ; i<=m ; i++){
for(int j=1 ; j<=n ; j++) cin>>s[i][j];
}
dp[1][1] = s[1][1];
for(int i=2 ; i<=m ; i++) dp[i][1] = dp[i-1][1] + s[i][1];
for(int i=2 ; i<=n ; i++) dp[1][i] = dp[1][i-1] + s[1][i];
for(int i=2 ; i<=m ; i++){
for(int j=2 ; j<=n ; j++){
dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + s[i][j];
}
}
cout<<dp[m][n]<<"\n";
}
P-6-7. LCS
bottom up
#include<bits/stdc++.h>
using namespace std;
int dp[505][505];
int main(){
string a,b;
cin>>a>>b;
int lena = a.size() , lenb = b.size();
for(int i=0 ; i<=lena ; i++) dp[i][0]=0;
for(int j=0 ; j<=lenb ; j++) dp[0][j]=0;
for(int i=1 ; i<=lena ; i++){
for(int j=1 ; j<=lenb ; j++){
if(a[i-1] == b[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
cout<<dp[lena][lenb]<<"\n";
}
Other
資訊之芽2022
Sprout 141
#include<bits/stdc++.h>
using namespace std;
int dp[100005][2];
int a[100005];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>a[i];
dp[1][0] = 0,dp[1][1]=a[1];
for(int i=2 ; i<=n ; i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = a[i] + dp[i-1][0];
}
cout<<max(dp[n][0],dp[n][1])<<"\n";
}
}
#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int a[100005];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>a[i];
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[3] + a[1];
for(int i=3 ; i<=n ; i++){
dp[i] = max(dp[i-2],dp[i-3]) + a[i];
}
cout<<max(dp[n],dp[n-1])<<"\n";
}
}
UVa
UVa 900 - Brick Wall Patterns
top down
#include<bits/stdc++.h>
using namespace std;
long long dp[55];
bool used[55];
long long f(int i){
if(used[i]) return dp[i];
used[i] = 1;
if(i==1) return dp[i] = 1LL;
if(i==2) return dp[i] = 2LL;
if(i==3) return dp[i] = 3LL;
return dp[i] = f(i-1) + f(i-2);
}
int main(){
int n;
while(cin>>n && n){
cout<<f(n)<<"\n";
}
}
UVa 11310 - DELIVERY DEBACLE
top down
#include<bits/stdc++.h>
using namespace std;
long long dp[45];
long long used[45];
long long f(int i){
if(used[i]) return dp[i];
used[i] = 1;
if(i==1) return dp[i] = 1LL;
if(i==2) return dp[i] = 5LL;
if(i==3) return dp[i] = 11LL;
return dp[i] = f(i-1) + f(i-2)*4 + f(i-3)*2;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
cout<<f(n)<<"\n";
}
}
ZJ d378: 最小路徑
bottom up
#include<bits/stdc++.h>
using namespace std;
int mp[105][105];
int dp[105][105];
int main(){
int n,m;
int cnt=1;
while(cin>>n>>m){
cout<<"Case #"<<cnt<<" :\n";
cnt++;
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j<=m ; j++){
cin>>mp[i][j];
}
}
dp[1][1] = 0;
for(int i=1 ; i<=n ; i++)
dp[i][1] = dp[i-1][1] + mp[i][1];
for(int j=1 ; j<=m ; j++)
dp[1][j] = dp[1][j-1] + mp[1][j];
for(int i=2 ; i<=n ; i++){
for(int j=2 ; j<=m ; j++)
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + mp[i][j];
}
cout<<dp[n][m]<<"\n";
}
}
