T1:A 先生有很多双筷子。确切的说应该是很多根,因为筷子的长度不一,很难判断出哪两根是一双的。这天,A 先生家里来了 K 个客人,A 先生留下他们吃晚饭。加上 A 先生,A 夫人和他们的孩子小 A,共 K+3 个人。每人需要用一双筷子。A 先生只好清理了一下筷子,共N 根,长度为 T1,T2,T3,......,TN.现在他想用这些筷子组合成 K+3 双,使每双的筷子长度差的平方和最小。(怎么不是和最小??这要去问 A 先生了,呵呵).
S1:①显然当n<(k+3)*2时无解.②依旧太菜,脑子断电了,一直想的是全排列式两两匹配导致DP推不出.其实可以先贪心的排序,相邻的两根筷子匹配才最优(跨越式匹配一定不是最优解).有了这个前提,dp就好推了.我们设f[ i ][ k ]为前 i 只筷子匹配成 k 能维护的最小平方和.f[ i ][ k ]=min{f[ i - 1][ k ],f[ i - 2 ][ k -1 ]+(ch[ i ] - ch[ i - 1]*(ch[ i ] - ch[ i - 1]),继承f[i - 1][ k ]是指这个筷子不选,继承前一个状态的最优值,与类似的' f[ i ][ 0 ] '来继承最优值.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define re register int n,k,ch[110],f[110][110]; int main() { freopen("CHOP.in","r",stdin); freopen("CHOP.out","w",stdout); scanf("%d%d",&n,&k);k+=3; for(re int i=1;i<=n;++i) scanf("%d",&ch[i]); if(n<k*2){puts("-1");return 0;} memset(f,0x7f,sizeof(f)); for(re int i=0;i<=n;++i) f[i][0]=0; for(re int i=2;i<=n;++i) for(re int j=1;j<=(i<<1);++j) f[i][j]=min(f[i-1][j],f[i-2][j-1]+(ch[i]-ch[i-1])*(ch[i]-ch[i-1])); printf("%d",f[n][k]); return 0; }
T2:护卫队
S2:如今写区间DP少有感觉的题,不过我真的要吐槽,不是说桥是单行道吗?不是汽车都最快的速度跑吗?速度慢的车能在速度快的车前面是咋回事?回归题目,我们设f[ i ][ j ]为区间[ i , j ]分为一组的最短时间.显然我们要由小的合法区间推出大的合法区间,这就决定了len从小到大推,且要放在最外层.接下来,枚举开头i,计算出结尾 j = i+len-1,枚举分割点k,由小区间推大区间即可,注意在循环中求区间最值用ST表.
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define e exit(0) #define re register #define LL long long const int maxn=1e5+10; double len,ans,f[1010][1010],st[maxn][21]; long long maxx,cnt,n,sum[1010],logn[maxn]; struct che{ double v; long long w; }car[1010]; inline void read(long long &x) { x=0;register long long f(0);register char ch(getchar()); while(!isdigit(ch))f|=(ch=='-'),ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=f?-x:x; } inline void double_read(double &x) { x=0;int f(0);char ch=getchar(); while(!isdigit(ch))f|=(ch=='-'),ch=getchar(); while(isdigit(ch))x=x*10+(ch^48),ch=getchar(); if(ch=='.') { int k(10);ch=getchar(); while(ch>='0'&&ch<='9') x+=1.0*(ch-'0')/k, k=(k<<1)+(k<<3), ch=getchar(); } x=f?-x:x; } inline int check(LL l,LL r) { LL sumw=sum[r]-sum[l-1]; if(sumw>maxx) return false; return true; } inline double ask(LL l,LL r) { LL s=logn[r-l+1]; return min(st[l][s],st[r-(1<<s)+1][s]); } inline void work() { logn[0]=-1; for(re LL i(1);i<=n;++i) st[i][0]=car[i].v,logn[i]=logn[i>>1]+1; for(re LL j=1;j<=20;++j) for(re LL i=1;i+(1<<j)-1<=n;++i) st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]); } int main() { freopen("CONVOY.in","r",stdin); freopen("CONVOY.out","w",stdout); read(maxx); double_read(len); read(n); for(re LL i(1);i<=n;++i) read(car[i].w),double_read(car[i].v), sum[i]=sum[i-1]+car[i].w, f[i][i]=double(len/car[i].v); work(); for(re LL i(1);i<=n;++i) for(re LL j=1;j<=n;++j){ if(i==j) continue; f[i][j]=100000000000000.0; } for(re LL lenth(2);lenth<=n;++lenth) for(re LL i(1);i+lenth-1<=n;++i){ LL j=i+lenth-1; if(check(i,j)){ double v=ask(i,j); f[i][j]=min(f[i][j],len/v); } for(re LL k(i);k<=j-1;++k) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); } ans=f[1][n]*60; printf("%.1lf",ans); return 0; }
T3:美元汇率
S3:DP水题.但题目也没将清每一次兑换全都换完啊!我们设f[ i ][ 0 ]表示第 i 天拥有的最多美元,f[ i ][ 1 ]表示第 i 天拥有的最大马克,注意有不兑换的情况(样例).
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register int n; double f[110][110],chang[110]; int main() { freopen("DOLLARS.in","r",stdin); freopen("DOLLARS.out","w",stdout); scanf("%d",&n); for(re int i=1;i<=n;++i){ scanf("%lf",&chang[i]); chang[i]/=100; } f[0][0]=100.0,f[0][1]=0.0; for(re int i=1;i<=n;++i){ f[i][0]=max(f[i-1][0],f[i-1][1]/chang[i]); f[i][1]=max(f[i-1][1],f[i-1][0]*chang[i]); } printf("%.2lf",f[n][0]); return 0; }
T4:胖男孩
S4:如题意,求三个字符串的最长公共子序列.有两个字符串的LCS我们可以很快得反应出来->相等前状态+1,不相等继承最优.对于输出对应字符串,我们可以类比ST表求LCA时对于求f[ i ][ j ]时的铺助坐标数组,跟着变换即可.
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define e exit(0) #define re register int lena,lenb,lenc,f[110][110][110]; string a,b,c,t[110][110][110]; int main() { freopen("FATBOY.in","r",stdin); freopen("FATBOY.out","w",stdout); cin>>a;cin>>b;cin>>c; lena=a.length(),lenb=b.length(),lenc=c.length(); for(re int i=1;i<=lena;++i) for(re int j=1;j<=lenb;++j) for(re int k=1;k<=lenc;++k){ if(a[i-1]==b[j-1]&&a[i-1]==c[k-1]){ if(f[i][j][k]<=f[i-1][j-1][k-1]+1){ f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+1); t[i][j][k]=t[i-1][j-1][k-1]+a[i-1]; } } else{ if(f[i-1][j][k]>=f[i][j-1][k]&&f[i-1][j][k]>=f[i][j][k-1]) t[i][j][k]=t[i-1][j][k]; else if(f[i][j-1][k]>=f[i-1][j][k]&&f[i][j-1][k]>=f[i][j][k-1]) t[i][j][k]=t[i][j-1][k]; else if(f[i][j][k-1]>=f[i-1][j][k]&&f[i][j][k-1]>=f[i][j-1][k]) t[i][j][k]=t[i][j][k-1]; f[i][j][k]=max(f[i-1][j][k],max(f[i][j-1][k],f[i][j][k-1])); } } cout<<t[lena][lenb][lenc]; return 0; }