五天每天刷了一dp
| CodeForces 455A Boredom |
定义 :dp[i]为取前i个元素后得到的最大值。则dp[i]=max(dp[i-1],dp[i-2]+a[i]*i);
写的时候愚蠢的分类讨论i元素是否选取。实际上第i-2个元素是否选取和状态dp[i]无关
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define ll __int64 const int maxn=100000; ll a[maxn+8]; ll dp[maxn+8][2]; int main() { int i,j,k,n; scanf("%d",&n); memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d",&k); a[k]++; } int x,y; for(i=1;i<=maxn;i++) { if(a[i]==0) dp[i][1]=max(dp[i-1][1],dp[i-1][0]); else dp[i][1]=max(dp[i-1][0]+a[i]*i,dp[i-1][1]); dp[i][0]=dp[i-1][1]; } printf("%I64d ",dp[maxn][1]); return 0; }
CodeForces 245H Queries for Number of Palindromes
给定一个字符串，q个询问，每个询问这个区间内有多少个回文串
区间dp统计数目即可
定义dp[i][j]为i到j的回文串总数
若s[i]==s[j]并且i+1~j-1段为回文串 dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]+1;
否则dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1];
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=5008; char s[maxn]; int dp[maxn][maxn]; bool papa[maxn][maxn]; int main() { int q; int i,j,k,n,m; scanf("%s",s+1); int len=strlen(s+1); memset(dp,0,sizeof(dp)); memset(papa,false,sizeof(papa)); for(i=1;i<=len;i++) { dp[i][i]=1;papa[i][i]=true;} for(i=1;i<len;i++) { if(s[i]==s[i+1]) { dp[i][i+1]=3; papa[i][i+1]=true; } else dp[i][i+1]=2; } for(k=2;k<len;k++) { for(i=1;i+k<=len;i++) { if(s[i]==s[i+k]&&papa[i+1][i+k-1]==true) { dp[i][i+k]=dp[i][i+k-1]+dp[i+1][i+k]+1-dp[i+1][i+k-1]; papa[i][i+k]=true; } else dp[i][i+k]=dp[i][i+k-1]+dp[i+1][i+k]-dp[i+1][i+k-1]; } } scanf("%d",&q); while(q--) { scanf("%d%d",&n,&m); printf("%d ",dp[n][m]); } return 0; }
CodeForces 437E The Child and Polygon
给定一个多边形求在题目条件下分割方式一共有多少种
依然区间dp统计个数.先把点都化成顺时针，若i,j之间的点k满足向量jk在向量ji的顺时针方，则dp[i][j]+=dp[i][k]*dp[k][j];
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ll __int64 const int maxn=208; const int mod=1e9+7; struct poi{ ll x,y; ll operator * (const poi &a) const { return x*a.y-y*a.x; } poi operator - (const poi &a) const { poi u; u.x=x-a.x; u.y=y-a.y; return u; } }f[maxn]; ll dp[maxn][maxn]; ll medp(int x,int y) { if(dp[x][y]!=-1) return dp[x][y]; if(y-x==1) return dp[x][y]=1; ll ans=0; for(int i=x+1;i<y;i++) if((f[x]-f[y])*(f[i]-f[y])>0) ans=(ans+medp(x,i)*medp(i,y))%mod; dp[x][y]=ans; return ans; } int main() { int i,j,n; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%I64d%I64d",&f[i].x,&f[i].y); ll ans=0; for(i=1;i<n;i++) { ans+=f[i]*f[i+1]; } ans+=f[n]*f[1]; if(ans<0) { poi shit; for(i=1;i<=(n>>1);i++) { shit=f[i]; f[i]=f[n-i+1]; f[n-i+1]=shit; } } memset(dp,-1,sizeof(dp)); medp(1,n); printf("%I64d ",dp[1][n]); return 0; }
CodeForces 77C Beavermuncher-0xFF
没想到用优先队列优化。代码不贴了。
| CodeForces 23E | Tree |
对于弱的神题，——
看了某神牛的代码，高精度模板很漂亮
主算法竟然一个后序遍历思想解决，学习了
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int mod=10000; const int st=80; const int maxn=710; const int maxm=2010; int pre[maxm],last[maxm],other[maxm],s[maxm]; int tot,n; struct bigint{ int a[st],n; bigint(){ }; bigint(int x) { memset(a,0,sizeof(a)); n=1,a[0]=x; } void init(int x) { n=1,a[0]=x; } bool operator<(const bigint &x) { if(n<x.n) return 1; else if(n>x.n) return 0; for(int i=n-1;i>=0;i--) if(a[i]<x.a[i]) return 1; else if(a[i]>x.a[i]) return 0; return 0; } bigint operator * (const bigint &x) { bigint t(0);t.n=x.n+n-1; for(int i=0;i<n;i++) for(int j=0;j<x.n;j++) t.a[i+j]+=a[i]*x.a[j]; for(int i=0;i<t.n;i++) { t.a[i+1]+=t.a[i]/mod; t.a[i]%=mod; } if(t.a[t.n]) t.n++; return t; } bigint operator + (const bigint x) { bigint t(0);t.n=max(x.n,n); for(int i=0;i<t.n;i++) { t.a[i]=t.a[i]+x.a[i]+a[i]; t.a[i+1]+=t.a[i]/mod; t.a[i]%=mod; } if(t.a[t.n]) ++t.n; return t; } void print(){ printf("%d",a[n-1]); for(int i=n-2;i>=0;i--) printf("%04d",a[i]); puts(" "); } }dp[maxn][maxn]; void add(int p,int q) { pre[++tot]=last[p]; last[p]=tot; other[tot]=q; } void dfs(int i,int f) { s[i]=1,dp[i][1].init(1),dp[i][0].init(0); for(int j=last[i];j;j=pre[j]) { int k=other[j]; if(k==f) continue; dfs(k,i); for(int p=s[i];p>=0;p--) { for(int q=s[k];q>=0;q--) { bigint c=dp[i][p]*dp[k][q]; if(dp[i][p+q]<c) dp[i][p+q]=c; } } s[i]+=s[k]; } for(int p=1;p<=s[i];p++) { bigint c(p); c=c*dp[i][p]; if(dp[i][0]<c) dp[i][0]=c; } } int main() { int i,j,u,v; scanf("%d",&n); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs(1,0); dp[1][0].print(); return 0; }