6道DP题只拿了220分，NOIp我不滚粗谁滚粗？
考试历程貌似并没有什么可说的QAQ，就是不停的来回推方程和写崩的状态中。
正经题解
六道题其实除了第六道比较恶心..其他的都还算可以。
truck
水题，不多说.
//DP truck
//by Cydiater
//2016.10.3
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "truck"
const int MAXN=1e3+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,K;
db R[MAXN],U[MAXN],C[MAXN],f[MAXN][MAXN],ans=0;
namespace solution{
void init(){
N=read();K=read();
up(i,0,K)scanf("%lf",&R[i]);
up(i,0,K)scanf("%lf",&U[i]);
up(i,0,K)scanf("%lf",&C[i]);
}
void DP(){
memset(f,0,sizeof(f));
up(i,1,N){
up(j,1,K)f[i][j]=max(f[i][j],f[i-1][j-1]+R[j-1]-U[j-1]);
up(j,0,K)f[i][1]=max(f[i][1],f[i-1][j]+R[0]-U[0]-C[j]);
}
}
void output(){
up(i,0,K)ans=max(ans,f[N][i]);
cout<<ans<<endl;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
DP();
output();
return 0;
}
带输出方案的版本..这个其实很好搞..比赛的时候好像把老师坑了
//DP truck
//by Cydiater
//2016.10.3
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "truck"
const int MAXN=1e3+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,K,id;
db R[MAXN],U[MAXN],C[MAXN],f[MAXN][MAXN],ans=0,sum=0;
bool choice[MAXN];
namespace solution{
void init(){
N=read();K=read();
up(i,0,K)scanf("%lf",&R[i]);
up(i,0,K)scanf("%lf",&U[i]);
up(i,0,K)scanf("%lf",&C[i]);
}
void DP(){
memset(f,0,sizeof(f));
up(i,1,N){
up(j,1,K)f[i][j]=max(f[i][j],f[i-1][j-1]+R[j-1]-U[j-1]);
up(j,0,K)f[i][1]=max(f[i][1],f[i-1][j]+R[0]-U[0]-C[j]);
}
}
void output(){
up(i,0,K){
if(f[N][i]>ans){
ans=f[N][i];
id=i;
}
ans=max(ans,f[N][i]);
}
printf("%.1lf\n",ans);
memset(choice,0,sizeof(choice));
down(i,N,1){
if(id==1){
choice[i]=1;
up(j,1,K)if(abs(f[i][1]-(f[i-1][j]+R[0]-U[0]-C[j]))<0.1){
id=j;
break;
}
}else id--;
}
choice[1]=0;
id=0;
up(k,1,N){
if(choice[k]!=1) id++;
else id=1;
printf("%d %d %.1lf\n",k,choice[k],f[k][id]-sum);
sum=f[k][id];
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
DP();
output();
return 0;
}
cleanup
很好的思路题。
当时写的时候还是太拿衣服了..，一眼DP方程$f[i]=min \{ f[j-1]+sum[i][j]^2 \}$。
这个平方呀，excited，再一眼数据范围，绝对是斜率优化（或者单调性优化），然后开始来回推方程。推到最后的时候悲惨的发现不满足斜率优化的条件，不甘心只拿暴力分（然而最后暴力分也没拿稳），又开始来回变形，无果。开始考虑单调性优化..两个小时过去了，无果。算了，随手码了个暴力，本来那个暴力是没问题的，后来写到第三题的时候加了个小优化QAQ，然后就炸了。
正解：
这个数据不管怎么给，答案不可能超过$N$（分$N$组即可）。所以最优解的每块对答案的贡献不可能超过$\sqrt{N}$，根据这个原理就可以对DP进行优化。
首先变形方程，$f[i]=min \{ f[b[j]-1]+j^2 \} j \in [1,\sqrt{N}]$，其中$b[j]$表示离$i$最近的（左），且满足$[b[j],i]$中不同的数字的个数不超过$j$个。
这时候我们如果能在$O(1)$的时间内求出$b[]$，就能在$O(N\sqrt{N})$的时间复杂度内求出本题答案。
如何在$O(1)$的时间内求出$b[]$?懒得说了，你搞个$pre[]$和$next[]$xjb搞搞就行了。
//NOIp DP cleanup
//by Cydiater
//2016.10.4
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "cleanup"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,a[MAXN],next[MAXN],tmp[MAXN],f[MAXN],lim,b[MAXN],pre[MAXN];
namespace solution{
void init(){
N=read();M=read();
memset(tmp,0,sizeof(tmp));
up(i,1,N){
a[i]=read();
next[i]=tmp[a[i]];
tmp[a[i]]=i;
}
memset(tmp,10,sizeof(tmp));
memset(pre,10,sizeof(pre));
down(i,N,1){
pre[i]=tmp[a[i]];
tmp[a[i]]=i;
}
lim=sqrt(1.0*N);
}
void DP(){
memset(f,10,sizeof(f));
memset(b,0,sizeof(b));
f[0]=0;f[1]=1;b[1]=1;
bool flag;
up(i,2,N){
flag=0;
up(j,1,min(lim,i)){
if(flag)break;
if(b[j]!=0&&b[j+1]==0){
if(next[i]<b[j])
b[j+1]=b[j];
flag=1;
}
if(next[i]>=b[j])continue;
else{
up(k,max(b[j],1),i-1)if(pre[k]>=i){
b[j]=k+1;
break;
}
}
}
up(j,1,min(lim,i))if(b[j]>0)f[i]=min(f[i],f[b[j]-1]+j*j);
}
}
void output(){
cout<<f[N]<<endl;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
DP();
output();
return 0;
}
wrk
水题，但是考场上写挂了，不说。
//DP wrk
//by Cydiater
//2016.10.3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "wrk"
const int MAXN=1e5+4;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int T,S,N,f[10005][105],Time[MAXN],ans=0;
struct Study{
int m,l,a;
}s[MAXN];
namespace solution{
void init(){
T=read();S=read();N=read();
up(i,1,S){
s[i].m=read()+1;
s[i].l=read();
s[i].a=read();
}
memset(Time,10,sizeof(Time));
up(i,1,N){
int c=read();
Time[c]=min(Time[c],read());
}
up(i,1,100)Time[i]=min(Time[i-1],Time[i]);
}
void slove(){
memset(f,-1,sizeof(f));
f[0][1]=0;
up(i,0,T){
up(j,1,100)if(f[i][j]>=0){
if(i+Time[j]<=T)f[i+Time[j]][j]=max(f[i+Time[j]][j],f[i][j]+1);
ans=max(ans,f[i][j]);
}
up(j,1,S)if(s[j].m==i+1&&i+s[j].l<=T&&f[i][j]>=0)f[i+s[j].l][s[j].a]=max(f[i+s[j].l][s[j].a],f[i][j]);
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
cout<<ans<<endl;
return 0;
}
exp
蛤省在11年省选的第一题，据说这一题稳妥A掉就进队了，弱省果然福利好....
其实这道题的关键不在于维护大小的关系，而在于维护相等的冲突。
首先，排除$x_i+y_i>N+1$这种显然不合法的情况，对于假设他们的值是从大到小排好序的，那么第$i$个人所属的区间显然就是$[x_i+1,N-y_i]$，也就是这个区间都是和这个人相等的人。
然后如果这个区间的人数大于这个区间的长度的话，那些超过的显然也是不合法的。
这时候问题就转化成了给你若干个区间，每个区间有一定的权值，要求用这些区间不重叠的覆盖线段且总权值和最大。到这里传统的DP就很容易解决了。
//NOIp DP exp
//by Cydiater
//2016.10.4
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "exp"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,LINK[MAXN],len=0,f[MAXN];
struct edge{
int y,next,v;
}e[MAXN];
namespace solution{
inline void insert(int x,int y){
for(int i=LINK[x];i;i=e[i].next)if(e[i].y==y){
if(e[i].v<x-y+1)e[i].v++;
return;
}
e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=1;
}
void init(){
N=read();
up(i,1,N){
int x=read(),y=read();
int leftt=x+1,rightt=N-y;
if(x+y>=N)continue;
insert(rightt,leftt);
}
}
void DP(){
memset(f,0,sizeof(f));
up(i,1,N){
f[i]=f[i-1];
for(int j=LINK[i];j;j=e[j].next)f[i]=max(f[i],f[e[j].y-1]+e[j].v);
}
}
void output(){
cout<<N-f[N]<<endl;
}
}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
using namespace solution;
init();
DP();
output();
return 0;
}
pyr
区间DP/分治 +乘法原理,很经典的一道题。
//NOIp pyr
//by Cydiater
//2016.10.3
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
const ll MAXN=1e3+5;
const ll oo=0x3f3f3f3f;
const ll mod=1000000000;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
char s[MAXN];
ll N,f[MAXN][MAXN];
namespace solution{
void init(){
scanf("%s",s+1);
N=strlen(s+1);
memset(f,-1,sizeof(f));
}
ll col(ll leftt,ll rightt){
if(f[leftt][rightt]!=-1) return f[leftt][rightt];
ll sum=0;
if((rightt-leftt+1)%2==0) return 0;
if(leftt==rightt) return 1;
int mid=(leftt+rightt)>>1;
bool flag=1;
if(s[leftt]==s[rightt]){
sum+=col(leftt+1,rightt-1);
up(i,leftt+1,rightt-1)
if(s[leftt]==s[i])
(sum+=col(leftt+1,i-1)*col(i,rightt)%mod)%=mod;
}
f[leftt][rightt]=sum;
return sum;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
cout<<col(1,N)<<endl;
return 0;
}
apo
考场上不会写的我只能现在写个题解了
//NOIp DP apo
//by Cydiater
//2016.10.4
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <iomanip>
#include <cmath>
using namespace std;
#define ll long long
#define up(i,j,n) for(ll i=j;i<=n;i++)
#define down(i,j,n) for(ll i=j;i>=n;i--)
#define FILE "apo"
const ll MAXN=1e6+5;
const ll oo=0x3f3f3f3f;
const ll mod=(1<<31)-1;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll f[25][10],leftt,rightt,mid,T;
namespace solution{
void pret(){
memset(f,0,sizeof(f));
f[0][0]=1;
up(i,1,21){
f[i][3]=f[i-1][3]*10+f[i-1][2];
f[i][2]=f[i-1][1];
f[i][1]=f[i-1][0];
f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])*9;
}
}
ll check(ll num){
ll di=0,far=1,tmp=0,cnt=0,ans=0;
for(;far<num;far*=10,di++);
while(tmp<num){
ll re_cnt;
while(tmp+far<=num){
tmp+=far;
if(cnt==3) re_cnt=3;
else if((tmp/far)%10==7) re_cnt=cnt+1;
else re_cnt=0;
down(i,3,3-re_cnt)ans+=f[di][i];
}
if(cnt!=3)cnt=((tmp/far)%10==6?cnt+1:0);
di--;far/=10;
}
return ans;
}
ll slove(ll N){
leftt=1;rightt=100000000000000000LL;
N--;
while(leftt+1<rightt){
mid=(leftt+rightt)>>1;
ll tmp=check(mid);
if(tmp>N) rightt=mid;
else leftt=mid;
}
if(check(leftt)==N) return leftt;
return rightt;
}
}
int main(){
freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
using namespace solution;
pret();
T=read();
while(T--)cout<<slove(read())<<endl;
return 0;
}