T1 青蛙的烦恼

⃢ — ⃢

$dis(i,j)$表示从点 i 到点 j 的距离

#include <bits/stdc++.h>
#define dis(a,b) (sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])))
using namespace std;
int n;
double x[1000],y[1000],f[1000][1000][2];
bool book[1000][1000][2];
double dfs(int cur,int l,int t)
{
if(book[cur][l][t])return f[cur][l][t];
book[cur][l][t]=1;
if(l==1)return 0;
if(!t)
f[cur][l][t]=
min(dfs(cur+l-1,l-1,1)+dis(cur,cur+l-1),dfs(cur+1,l-1,0)+dis(cur,cur+1));
else
f[cur][l][t]=
min(dfs(cur-l+1,l-1,0)+dis(cur,cur-l+1),dfs(cur-1,l-1,1)+dis(cur,cur-1));
return f[cur][l][t];
}
int main()
{
freopen("frog.in","r",stdin),freopen("frog.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
printf("%.3f\n",dfs(1,n,0));
return 0;
}


T2 警卫安排

//以上截图自 ppt

#include <bits/stdc++.h>
using namespace std;
int n,v[1000],root,f[1000][3];
bool book[1000];
vector<int> g[1000];
int dfs(int u,int w)
{
if(f[u][w]!=-1)return f[u][w];
switch(f[u][w]=0,w)
{
case 0:
for(int i=0;i<g[u].size();i++)
f[u][w]+=min(dfs(g[u][i],0),min(dfs(g[u][i],1),dfs(g[u][i],2)));
f[u][w]+=v[u];break;
case 1:
for(int i=0;i<g[u].size();i++)f[u][w]+=min(dfs(g[u][i],0),dfs(g[u][i],2));
break;
case 2:
f[u][w]=1e8;
for(int i=0;i<g[u].size();i++)
f[u][w]=min(f[u][w],dfs(g[u][i],0)-min(dfs(g[u][i],0),dfs(g[u][i],2)));
for(int i=0;i<g[u].size();i++)
f[u][w]+=min(dfs(g[u][i],0),dfs(g[u][i],2));
break;
}
return f[u][w];
}
int main()
{
freopen("security.in","r",stdin),freopen("security.out","w",stdout);
scanf("%d",&n);
for(int i=1,j,k;i<=n;i++)
{
scanf("%d",&j),scanf("%d%d",&v[j],&k);
for(int i1=1,j1;i1<=k;i1++)scanf("%d",&j1),g[j].push_back(j1),book[j1]=1;
}
for(int i=1;i<=n;i++)if(!book[i]){root=i;break;}
memset(f,-1,sizeof(f)),printf("%d\n",min(dfs(root,0),dfs(root,2)));
return 0;
}


T3 最长上升子序列

#include <bits/stdc++.h>
using namespace std;
int n,k,a[200005],e[200005],cnt,f[200005],ans;
int main()
{
freopen("lis.in","r",stdin),freopen("lis.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=k;i++)
{
f[i]=(int)(lower_bound(e+1,e+1+cnt,a[i])-e);
if(f[i]>cnt)e[++cnt]=a[i];else if(a[i]<e[f[i]])e[f[i]]=a[i];
}
memset(e,0,sizeof(e)),cnt=0;
for(int i=k+1;i<=n;i++)
if(a[i]>a[k])
{
f[i]=(int)(lower_bound(e+1,e+1+cnt,a[i])-e);
if(f[i]>cnt)e[++cnt]=a[i];else if(a[i]<e[f[i]])e[f[i]]=a[i];
ans=max(ans,f[i]);
}
printf("%d\n",ans+f[k]);
return 0;
}


T4 最短回文串

#include <bits/stdc++.h>
using namespace std;
int n,f[5005][5005];
char s[5005];
int main()
{
freopen("palindrome.in","r",stdin),freopen("palindrome.out","w",stdout);
scanf("%d%s",&n,s);
for(int l=1;l<n;l++)
for(int i=0;i+l<n;i++)
{
f[i][i+l]=min(f[i+1][i+l],f[i][i+l-1])+1;
if(s[i]==s[i+l])f[i][i+l]=min(f[i][i+l],f[i+1][i+l-1]);
}
printf("%d\n",f[0][n-1]);
return 0;
}