期望得分：100+30+100=230
实际得分：100+30+70=200
T3 数组开小了 。。。。。
记录 1的前缀和，0的后缀和
枚举第一个1的出现位置
#include#include #include #define N 100002using namespace std;char s[N];int num[N];int suf0[N],pre1[N];int main(){ freopen("reverse.in","r",stdin); freopen("reverse.out","w",stdout); scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;i++) num[i]=s[i]-'0'; for(int i=1;i<=len;i++) pre1[i]=pre1[i-1]+num[i]; for(int i=len;i;i--) suf0[i]=suf0[i+1]+(!num[i]); int ans=len; for(int i=1;i<=len;i++) ans=min(ans,pre1[i-1]+suf0[i]); ans=min(ans,pre1[len]); printf("%d",ans);}
从1——n枚举一遍
二进制表示它有哪些数出现过了，相当于哈希
然后Σ C（i，2）
#includeusing namespace std;int f[1026];void count(int x){ int s=0; while(x) { s|=1<
考场思路：
种类只有2^9种可能
所以枚举每一种可能
那问题转化为了 有x种数，用它来组成<=n的数的方案数
开始想裸的数位DP，但它不能保证所有的x种数都用上
然后又改的状压DP，dp[i][j] 表示填了i位，使用数的状态为j，
虽然能保证所有的x种数都用上，但数位DP的作用难以体现：
若枚举这一位填哪个数，因为不知道前面填了什么，所以也不能确定这一位填什么
脑补的改进方法是 数位DP加一维表示状态，状压DP加一维表示上一位填了什么
可行性未知
考场错误的状压DP
#include#include using namespace std;int tmp[10],num[10];int use[10],dp[10][1024];int a[10],b[10];int main(){ int n,len=0; scanf("%d",&n); if(n<10) { printf("0"); return 0; } while(n) { tmp[++len]=n%10; n/=10;} for(int i=len,len=0;i;i--) num[++len]=tmp[i]; int tot,sum,T; long long ans=0; num[0]=10; for(int s=2;s<1023;s++) { if(s==2) { int sad=4; } memset(use,false,sizeof(use)); tot=0; memset(b,0,sizeof(b)); memset(dp,0,sizeof(dp)); for(int i=0;i<10;i++) if(s&(1<
考场错误的数位DP
#include#include using namespace std;int tmp[10],num[10];int dp[10][10][10][2];bool use[10];int main(){ int n,len=0; scanf("%d",&n); if(n<10) { printf("0"); return 0; } while(n) { tmp[++len]=n%10; n/=10;} for(int i=len,len=0;i;i--) num[++len]=i; int S=1<<10; long long tot,ans=0; for(int s=S-1;s;s=s&(s-1)) { memset(use,false,sizeof(use)); memset(dp,0,sizeof(dp)); for(int i=0;i<10;i++) if(s&(1<
30暴力
#include#include bool visx[10];bool visy[10];using namespace std;int main(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout); int n; scanf("%d",&n); int X,Y,sx,sy,ans=0; bool ok; for(int x=1;x
贪心
肯定是上升的时候，越大越好
下降的时候，越小越好
所以有了初步思路：
每次找连续下降的最后一个，然后找连续上升的最后一个，循环往复
看似很正确
但请看下图：
假设k=2，如果按上面的思路，那么后面会选上9
接下来要找连续下降 9后面那个点和8都不满足k=2的差值
所以我们得到的答案=4
但最优解是不要9，选后面的12和8
因为9后面的那个点不能下降，所以到了12仍然是处于上升，所以12比9更优
所以，我们不能找连续的序列，而是
只要现在处于上升阶段，就找最大的
只要现在处于下降阶段，就找最小的
幸亏打了暴力，对拍拍出了这个bug
#include#include #include #define N 1000001using namespace std;int e[N];void read(int &x){ x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}int main(){ freopen("wave.in","r",stdin); freopen("wave.out","w",stdout); int n,k; read(n); read(k); for(int i=1;i<=n;i++) read(e[i]); bool up=true; int now,len=1; for(now=1;now<=n && e[now+1]<=e[now];now++); int last=e[now++]; while(now<=n) { if(!up) { while(now<=n) { if(last-e[now]>=k) { last=e[now]; len++; up^=1; break; } else if(e[now]>=last ) last=e[now]; now++; } } else { while(now<=n) { if(e[now]-last>=k) { last=e[now]; len++; up^=1; break; } else if(e[now]<=last) last=e[now]; now++; } } now++; } printf("%d",len);}
对拍代码（n^2）
#include#include #include #define N 1000001using namespace std;int f[N][2],a[N];void read(int &x){ x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}int main(){ freopen("data.in","r",stdin); freopen("std.out","w",stdout); int n,k; read(n); read(k); for(int i=1;i<=n;++i) read(a[i]); int mx,ans=0; for(int i=1;i<=n;i++) { mx=0; for(int j=i-1;j;j--) if(a[j]-a[i]>=k) mx=max(mx,f[j][1]); f[i][0]=mx+1; ans=max(ans,f[i][0]); mx=0; for(int j=i-1;j;j--) if(a[i]-a[j]>=k) mx=max(mx,f[j][0]); if(mx) { f[i][1]=mx+1; ans=max(ans,f[i][1]); } } printf("%d",ans);}