# T1

## 青蛙的烦恼

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
double x[730],y[730],f[730][730],g[730][730];
int n;
double dis(int a,int b){
double kl1=x[a]-x[b],kl2=y[a]-y[b];
return sqrt(kl1*kl1+kl2*kl2);
}
int main()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
for(i=n;i>=1;i--)
for(j=i+1;j<=n;j++){
f[i][j]=min(f[i+1][j]+dis(i+1,i),g[i+1][j]+dis(i,j));
g[i][j]=min(f[i][j-1]+dis(i,j),g[i][j-1]+dis(j,j-1));
}
printf("%.3lf",f[1][n]);
return 0;
}


# T2

## 警卫安排

$$f(i,0)= \sum min(f(son,0),f(son,1),f(son,2));$$
$$f(i,1)= \sum min(f(son,0),f(son,2));f$$
$$f(i,2)= \sum min(f(son,0),f(son,2))+f(k,0);$$，k 是 i 的子节点之一

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define ll long long
const int maxn=730;
ll w[maxn],f[maxn][3];
int h[maxn],to[maxn],ne[maxn];
bool is[maxn];
int n,rot,tot;
void dfs(int x){
int i,bj=0;
for(i=h[x];i;i=ne[i]){
dfs(to[i]);bj=1;
f[x][1]+=min(f[to[i]][0],f[to[i]][2]);
f[x][0]+=min(f[to[i]][0],min(f[to[i]][2],f[to[i]][1]));
}
f[x][2]=INT_MAX;
for(i=h[x];i;i=ne[i])
f[x][2]=min(f[x][2],f[x][1]-min(f[to[i]][0],f[to[i]][2])+f[to[i]][0]);
f[x][0]+=w[x];
}
int main()
{
int i,j,num,x,y;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x);scanf("%lld%d",&w[x],&num);
for(j=1;j<=num;j++)
}
for(i=1;i<=n;i++)if(!is[i]){rot=i;break;}
dfs(rot);
printf("%lld",min(f[rot][0],f[rot][2]));
return 0;
}


# T3

## 最长上升子序列

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define ll long long
ll q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')
q=(ll)q*10+(ll)(ch-'0'),ch=getchar();
return q;
}
int n,m,tot,bj=-1;
ll a[200005],b[200005];
int main()
{
int i,j,kl;
for(i=1;i<=n;i++){
kl=lower_bound(b+1,b+1+tot,a[i])-b;
if(kl>tot)tot++;
if(kl<=bj)continue;b[kl]=a[i];
if(i==m){tot=kl;bj=kl;}
}
printf("%d",tot);
return 0;
}


# T4

## 最短回文串

abcdcba，abcddbca 就是回文串，而 abcdabcd 不是。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
int n,f[5005][5005];char a[5005];
int main()
{
int i,j,t;
scanf("%d\n%s",&n,a);
for(i=n;i>=1;i--)
for(j=i+1;j<=n;j++){
if(a[i-1]==a[j-1])f[i][j]=f[i+1][j-1];
else f[i][j]=min(f[i+1][j],f[i][j-1])+1;
}
printf("%d",f[1][n]);
return 0;
}