A - Frog 1/B - Frog 2
入门...
#include<cstdio>
#define abs(a) ((a)>=0?(a):(-(a)))
#define min(a,b) ((a)<(b)?(a):(b))
#define maxn 100050
using namespace std;
int dp[maxn],a[maxn];
int main(){
int n,k=;
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",&a[i]),dp[i]=1e9;
dp[]=;
for (int i=;i<=n;i++){
for (int j=;j<=k;j++)
if (i-j>) dp[i]=min(dp[i],dp[i-j]+abs(a[i-j]-a[i]));
}
printf("%d\n",dp[n]);
return ;
}
A and B
C - Vacation
$dp[i][0/1/2]$ 表示到第 $i$ 个 这一个选 $0/1/2$ 转移就很显然了....
#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
#define maxn 100050
using namespace std;
int dp[maxn][];
int main(){
int n;
scanf("%d",&n);
for (int i=;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
dp[i][]=max(dp[i-][],dp[i-][])+a;
dp[i][]=max(dp[i-][],dp[i-][])+b;
dp[i][]=max(dp[i-][],dp[i-][])+c;
}
printf("%d\n",max(max(dp[n][],dp[n][]),dp[n][]));
return ;
}
C
D - Knapsack 1
裸背包
#include<cstdio>
#define ll long long
#define max(a,b) (a>b?a:b)
#define maxn 100050
using namespace std;
ll dp[maxn];
int main(){
int n,W;
scanf("%d%d",&n,&W);
for (int i=;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
for (int j=W;j>=a;j--)
dp[j]=max(dp[j-a]+b,dp[j]);
}
ll ans=;
for (int j=;j<=W;j++)
if (dp[j]>ans) ans=dp[j];
printf("%lld\n",ans);
return ;
}
D
E - Knapsack 2
发现价值比较小，那么换一下 $dp$ 的状态表示
$dp[j]$ 表示价值为 $j$ 的最小重量
答案就从大到小枚举 $\leq W$ 的即可。
#include<cstdio>
#define ll long long
#define max(a,b) (a>b?a:b)
#define maxn 100050
#define min(a,b) (a<b?a:b)
using namespace std;
ll dp[maxn];
int main(){
int n,W;
scanf("%d%d",&n,&W);
for (int j=;j<=1e5;j++)
dp[j]=1e12;
for (int i=;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
for (int j=1e5;j>=b;j--)
dp[j]=min(dp[j-b]+a,dp[j]);
}
for (int i=1e5;i>=;i--)
if (dp[i]<=W) return printf("%d\n",i),;
return ;
}
/*
dp[i][j]表示前i个价值和为j的最小重量
*/
E
F - LCS
裸的最长公共子序列...方案存一下转移路径倒推就好了
#include<cstdio>
#include<cstring>
#define maxn 3005
using namespace std;
int dp[maxn][maxn],last[maxn][maxn];
char s[maxn],t[maxn],w[maxn];
int main(){
scanf("%s%s",s+,t+);
int n=strlen(s+),m=strlen(t+);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++){
if (s[i]==t[j]) {
if (dp[i][j]<dp[i-][j-]+) dp[i][j]=dp[i-][j-]+,last[i][j]=;
}
if (dp[i-][j]>dp[i][j]) dp[i][j]=dp[i-][j],last[i][j]=;
if (dp[i][j-]>dp[i][j]) dp[i][j]=dp[i][j-],last[i][j]=;
}
int x=n,y=m;
while (dp[x][y]){
if (last[x][y]==) w[dp[x][y]]=s[x],x--,y--;else
if (last[x][y]==) x--;else y--;
}
for (int i=;i<=dp[n][m];i++)
printf("%c",w[i]);
printf("\n");
return ;
}
F
G - Longest Path
最长路径，拓扑上dp
#include<cstdio>
#define maxn 100050
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
struct enode{
int nxt,y;
}e[maxn];
int ans=,tot=;
int n,m;
int q[maxn],dp[maxn],first[maxn],goin[maxn];
void adde(int x,int y){
e[tot].nxt=first[x];
e[tot].y=y;
first[x]=tot++;
goin[y]++;
}
void tupu(){
int head=,tail=;
for (int i=;i<=n;i++)
if (!goin[i]) q[++tail]=i;
while (head<=tail){
int x=q[head++];
if (dp[x]>ans) ans=dp[x];
for (int i=first[x];i>=;i=e[i].nxt){
int y=e[i].y;
goin[y]--;
dp[y]=max(dp[x]+,dp[y]);
if (!goin[y]) q[++tail]=y;
}
}
}
int main(){ scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
first[i]=-;
for (int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
adde(x,y);
}
tupu();
printf("%d\n",ans);
return ;
}
G
H - Grid 1
唔...入门dp吧QAQ
#include<cstdio>
#define HR 1000000007
using namespace std;
char s[];
int dp[][];
int main(){
int n,m;
scanf("%d%d",&n,&m);
dp[][]=;
for (int i=;i<=n;i++){
scanf("%s",s+);
for (int j=;j<=m;j++)
if ((i!=||j!=)&&(s[j]!='#')) dp[i][j]=(dp[i-][j]+dp[i][j-])%HR;
}
printf("%d\n",dp[n][m]);
return ;
}
H
I - Coins
概率dp
$dp[i][j]$ 表示前 $i$ 个有 $j$ 个向上的概率
那么对于当前这一个 要不然就向上 要不然就向下
$dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])$
#include<cstdio>
using namespace std;
double p[],dp[][];
int main(){
int n;
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%lf",&p[i]);
dp[][]=;
for (int i=;i<=n;i++){
dp[i][]=dp[i-][]*(-p[i]);
for (int j=;j<=i;j++)
dp[i][j]=dp[i-][j-]*p[i]+dp[i-][j]*(-p[i]);
} double ans=;
for (int i=;i<=n;i++)
if (i>n-i) ans+=dp[n][i];
printf("%.10lf\n",ans);
return ;
}
I
J - Sushi
期望dp
$dp[i][j][k]$ 表示 $1$ 有 $i$ 个,$2$ 有 $j$ 个,$3$ 有 $k$ 个的期望
$dp[i][j][k]=dp[i-1][j][k]\times \frac{i}{n}+dp[i+1][j-1][k]\times \frac{j}{n}+dp[i][j+1][k-1]\times \frac{k}{n}+dp[i][j][k]\times \frac{n-i-j-k}{n}+1$
$dp[i][j][k]\times \frac{i+j+k}{n}=dp[i-1][j][k]\times \frac{i}{n}+dp[i+1][j-1][k]\times \frac{j}{n}+dp[i][j+1][k-1]\times \frac{k}{n}+1$
$dp[i][j][k]\times(i+j+k)=dp[i-1][j][k]\times i+dp[i+1][j-1][k]\times j+dp[i][j+1][k-1]\times k+n$
$dp[i][j][k]=dp[i-1][j][k]\times \frac{i}{i+j+k}+dp[i+1][j-1][k]\times \frac{j}{i+j+k}+dp[i][j+1][k-1]\times \frac{k}{i+j+k}+\frac{n}{i+j+k}$
#include<cstdio>
using namespace std;
double dp[][][];
int a[];
int main(){
int n;
scanf("%d",&n);
for (int i=;i<=n;i++){
int x;
scanf("%d",&x);
a[x]++;
}
for (int k=;k<=n;k++)
for (int j=;j<=n;j++)
for (int i=;i<=n;i++)
if (i||j||k) {
if (i) dp[i][j][k]+=dp[i-][j][k]*i/(i+j+k);
if (j) dp[i][j][k]+=dp[i+][j-][k]*j/(i+j+k);
if (k) dp[i][j][k]+=dp[i][j+][k-]*k/(i+j+k);
dp[i][j][k]+=(double)n/(i+j+k);
}
printf("%.15lf\n",dp[a[]][a[]][a[]]);
return ;
} /*
dp[i][j][k]表示当前有i个1 j个2 k个3 的期望步数 dp[0][0][0]=0 dp[i][j][k]=dp[i-1][j][k]*i/n+dp[i+1][j-1][k]*j/n+dp[i][j+1][k-1]*k/n+dp[i][j][k]*(n-i-j-k)/n+1
dp[i][j][k]*(i+j+k)/n=dp[i-1][j][k]*i/n+dp[i+1][j-1][k]*j/n+dp[i][j+1][k-1]*k/n+1
dp[i][j][k]*(i+j+k)=dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k+n
dp[i][j][k]=dp[i-1][j][k]*i/(i+j+k)+dp[i+1][j-1][k]*j/(i+j+k)+dp[i][j+1][k-1]*k/(i+j+k)+n/(i+j+k) */
J