DP小合集

扫码查看

1.Uva1625颜色的长度

dp[i][j]表示前一个串选到第i个 后一个串选到第j个 的最小价值

记一下还有多少个没有结束即dp2

记一下每个数开始和结束的位置

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
char s1[],s2[];
int fp[],fq[],ep[],eq[];
const int INF=;
int dp1[][],dp2[][];
int main()
{
//freopen("color.in","r",stdin);
//freopen("color.out","w",stdout);
//写了个意义不明的滚动数组。。。
//BGM:Hop
scanf("%s%s",s1+,s2+);
int n=strlen(s1+),m=strlen(s2+);
for(int i=;i<=n;i++)s1[i]-='A';
for(int i=;i<=m;i++)s2[i]-='A';
for(int i=;i<;i++)fp[i]=fq[i]=INF;
for(int i=;i<=n;i++)
{
fp[s1[i]]=min(fp[s1[i]],i);
ep[s1[i]]=i;
}
for(int i=;i<=m;i++)
{
fq[s2[i]]=min(fq[s2[i]],i);
eq[s2[i]]=i;
}
int cur=;
for(int i=;i<=n+;i++)
{
for(int j=;j<=m+;j++)
{
if(!i && !j)continue;
int v1=INF,v2=INF;
if(i)v1=dp1[cur^][j]+dp2[cur^][j];
if(j)v2=dp1[cur][j-]+dp2[cur][j-];
dp1[cur][j]=min(v1,v2);
if(i)
{
dp2[cur][j]=dp2[cur^][j];
if(fp[s1[i]]==i&&fq[s1[i]]>j)dp2[cur][j]++;
if(ep[s1[i]]==i&&eq[s1[i]]<=j)dp2[cur][j]--;
}
else if(j)
{
dp2[cur][j]=dp2[cur][j-];
if(fq[s2[j]]==j&&fp[s2[j]]>i)dp2[cur][j]++;
if(eq[s2[j]]==j&&ep[s2[j]]<=i)dp2[cur][j]--;
}
}
cur=cur^;
}
cout<<dp1[cur^][m];
return ;
}

意义不明的滚动数组

2.Uva12563劲歌金曲

首先留出1s来唱最后一首歌

剩下的简单的背包+记录路径

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=;
int n,T;
int a[MAXN];
int w[];
int b[MAXN];
int main()
{
freopen("party.in","r",stdin);
freopen("party.out","w",stdout);
cin>>n>>T;
for(int i=;i<n;i++)cin>>w[i];
T=min(T,);
T--;//长者续命-1s 苟利国家生死以岂因祸福避趋之 敢同恶鬼争高下,不向霸王让寸分
//你们啊Naive!你们有一个好 全世界到哪个地方你们比其他的西方记者跑的还快
//美国的华莱士不知比你们高到哪里去了我跟他谈笑风生
sort(w,w+n);
for(int i=;i<n;i++)
for(int j=T;j>=w[i];j--)
if((b[j]<b[a[j-w[i]]]+) || (b[j]==b[a[j-w[i]]]+ && a[j]<a[j-w[i]]+w[i]) )
{
a[j]=a[j-w[i]]+w[i];
b[j]=b[a[j-w[i]]]+;
}
b[T]++;
cout<<b[T]<<" "<<a[T]+;
return ;
}

-1s很重要

3.回文子串

把一个字符串切成若干回文子串 问最少切多少个

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=;
const int INF=;
int dp[MAXN];
char s[MAXN];
bool judge(int i,int j)
{
while(i<j)if(s[i++]!=s[j--])return false;
return true;
}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%s",s+);
dp[]=;
int len=strlen(s+);
for(int i=;i<=len;i++)dp[i]=INF; for(int i=;i<=len;i++)
for(int j=;j<=i;j++)
if(judge(j,i))dp[i]=min(dp[i],dp[j-]+); printf("%d\n",dp[len]); return ;
}

直接上代码吧= =

4.切木棍

有一个长为L的棍子,还有n个切割点的位置(按从小到大排列)。你的任务是在这些切割点的位置处把棍子切成n+1部分,使得总切割的费用最少。每次切割的费用等于被切割的木棍长度。

区间dp

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int l,n;
const int inf=;
int dp[][];
int a[];
int main()
{
freopen("stick.in","r",stdin);
freopen("stick.out","w",stdout);
scanf("%d%d",&l,&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);a[]=;a[n+]=l;
sort(a+,a+n+);
for(int len=;len<=n+;len++)
for(int i=;i<=n+-len;i++)
{
dp[len][i]=inf;
for(int j=;j<=len-;j++)dp[len][i]=min(dp[len][i],dp[j][i]+dp[len-j][i+j]+a[len+i]-a[i]);
}
cout<<dp[n+][];
}

似乎发过的= =

5.走过去再走回来

给定平面上n个点(横坐标严格递增)你要从最左边走到最右边再走回来 走欧几里得距离 而且要求每个点都走到 求走的最短路

一开始到洗手间数学证明了半天。。。后来发现还是鸡神设计的状态好(Orz Jackyyc)

dp[i][j]表示前面的人走到i 后面的人走到j 且1~i每个点都走过了

然后记忆化搜索嗖嗖嗖就出来了

再次Orz Jackyyc

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
char ch=getchar();
int x=,f=;
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=*x+ch-'';ch=getchar();}
return x*f;
}
const double eps=1e-;
struct point
{
double x,y;
}p[];
double d(point a,point b)
{
double ans=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return ans;
}
int n;
double dp[][];
double dis[][];
double Dp(int a,int b)
{
if(dp[a][b])return dp[a][b];
else return dp[a][b]=min(Dp(a+,b)+dis[a][a+],Dp(a+,a)+dis[b][a+]);
}
int ans=2147483647.0;
int main()
{
freopen("route.in","r",stdin);
freopen("route.out","w",stdout);
n=read();
for(int i=;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=;i<=n;i++)for(int j=;j<=n;j++)dis[i][j]=d(p[i],p[j]);
for(int i=;i<n-;i++)dp[n-][i]=dis[n-][n]+dis[i][n];
double ans=Dp(,); printf("%.2lf",ans);
return ;
}

6.城市里的间谍uva1025
预处理比较烦

judge[t][i][0]表示在时间t 车站i 有一个向左开的车

judge[t][i][1]表示在时间t 车站i 有一个向右开的车

对于每个时间 有三个决策 不动 朝左 朝右

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
char ch=getchar();
int x=,f=;
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=*x+ch-'';ch=getchar();}
return x*f;
}
const int INF=;
int n,m,T,M;
const int maxn=;
int t[maxn],d[maxn],D[maxn];
bool judge[maxn][maxn][];
int dp[maxn][maxn];
int main()
{
freopen("spy.in","r",stdin);
freopen("spy.out","w",stdout);
scanf("%d%d",&n,&T);
for(int i=;i<=n-;i++)scanf("%d",&t[i]);
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d",&d[i]);
int te=d[i];
if(d[i]<T)judge[d[i]][][]=;
for(int j=;j<=n-;j++)
{
if(te+t[j]<=T)
{
judge[te+t[j]][j+][]=;
te=te+t[j];
}
else break;
}
}
scanf("%d",&M);
for(int i=;i<=M;i++)
{
scanf("%d",&D[i]);
int te=D[i];
if(D[i]<T)judge[D[i]][n][]=;
for(int j=n-;j>=;j--)
{
if(te+t[j]<=T)
{
judge[te+t[j]][j][]=;
te=te+t[j];
}
else break;
}
}
for(int i=;i<=n-;i++)dp[T][i]=INF;
dp[T][]=;
for(int i=T-;i>=;i--)
{
for(int j=;j<=n;j++)
{
dp[i][j]=dp[i+][j]+;
if(j<n && judge[i][j][] && i+t[j]<=T)dp[i][j]=min(dp[i][j],dp[i+t[j]][j+]);
if(j> && judge[i][j][] && i+t[j-]<=T)dp[i][j]=min(dp[i][j],dp[i+t[j-]][j-]);
}
}
if(dp[][]>=INF)cout<<"impossible";
else cout<<dp[][];
}
05-11 17:03
查看更多