A. 小奇挖矿2
显然的O(m)dp：$f[i]=max(f[i-4],f[i-7])+a[i]$，当然你要保证i，i-4，i-7都能到达
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
const int MAXN=1e7+5;
int n,m,a[MAXN],b[MAXN],ans=0,f[MAXN];
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
f[b[i]]+=a[i];
}
for(int i=0;i<=3;i++) f[i]=-1;
for(int i=5;i<=6;i++) f[i]=-1;
ans=max(f[4],f[7]);
for(int i=8;i<=m;i++){
if(f[i-4]==-1&&f[i-7]==-1){
f[i]=-1;
continue;
}
f[i]+=max(f[i-4],f[i-7]);
ans=max(ans,f[i]);
}
printf("%d
",ans);
return 0;
}
然后我们优化，我们发现如果两点之间的距离超过18就一定能到达，所以我们把距离压缩一下
具体为什么你需要做一下NOIP2017小凯的疑惑
然后就AC了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
const int MAXN=2e6+5;
int n,m,a[MAXN],b[MAXN],ans=0,f[MAXN];
struct node{
int a,b;
friend bool operator < (node x,node y){
return x.b==y.b?x.a<y.a:x.b<y.b;
}
}mine[MAXN];
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&mine[i].a,&mine[i].b);
sort(mine+1,mine+n+1);
for(int i=1;i<=n;i++){
if(mine[i].b-mine[i-1].b>17)
a[i]=mine[i].a,b[i]=b[i-1]+18;
else a[i]=mine[i].a,b[i]=b[i-1]+(mine[i].b-mine[i-1].b);
}
for(int i=1;i<=n;i++) f[b[i]]+=a[i];
for(int i=0;i<=3;i++) f[i]=-1;
for(int i=5;i<=6;i++) f[i]=-1;
m=b[n];
ans=max(f[4],f[7]);
for(int i=8;i<=m;i++){
if(f[i-4]==-1&&f[i-7]==-1){
f[i]=-1;
continue;
}
f[i]+=max(f[i-4],f[i-7]);
ans=max(ans,f[i]);
}
printf("%d
",ans);
return 0;
}
还有一种解决方法：
将所有矿物排序，f[i]为到第i个矿体能获得的最大原矿数，那么f[i]=max{f[j]}+x[i]，其中，i-j满足能拆分成4和7。
这样dp需要n2的复杂度，但是我们发现，相距超过17的一定可达，那么不超过17的范围内暴力，超过17的取个最大值即可，复杂度O(n)
from skyh：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e5+10;
map<int,int> mp;
int n,m,ans,cnt;
int dp[N],mx[N];
bool ok[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0};//0 4 7 8 11 12 14 15 16 >17
inline int read(register int x=0,register char ch=getchar(),bool ff=0){
while(!isdigit(ch)) ff=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return ff?-x:x;
}
struct node{
int val,pos;
friend bool operator < (const node &a,const node &b){
return a.pos<b.pos;
}
}k[N];
int main(){
//freopen("x.in","r",stdin);
//freopen("me.out","w",stdout);
n=read(); m=read();
for(int i=1,v,p,o;i<=n;++i){
v=read(),p=read();
if(!mp[p]) mp[p]=++cnt;
o=mp[p]; k[o].pos=p; k[o].val+=v;
}
sort(k+1,k+cnt+1);
memset(dp,-0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=cnt;++i){
for(int j=i-1;~j;--j){
if(k[i].pos-k[j].pos<=17&&ok[k[i].pos-k[j].pos]) dp[i]=max(dp[i],dp[j]+k[i].val);
if(k[i].pos-k[j].pos>17){
dp[i]=max(dp[i],mx[j]+k[i].val);
break;
}
}
ans=max(ans,dp[i]);
mx[i]=max(mx[i-1],dp[i]);
}
printf("%d
",ans);
return 0;
}
B：小奇的矩阵(matrix)
平均数这玩意显然可拆：令$sum=sum A_i$，$sqr=sum A_{i}^{2}$
$Aavg=frac{sum}{n+m-1}$
所以：原式=$(n+m-1)*sqr-sum^2$，推一下就能推出来
然后。。。我竟然去想了搜索！
正解dp：设$f[s][i][j]$表示到了点(i,j)，总和为s时的最小sqr值
所以f[s][i][j]=min(f[s-a[i][j]][i][j-1]+a[i][j]*a[i][j],f[s-a[i][j]][i-1][j]+a[i][j]*a[i][j]);
然后就做出来了
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
#define re register
using namespace std;
int t,n,m,a[35][35],ans,f[1805][35][35];
signed main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(re int i=1;i<=n;i++)
for(re int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
ans=inf;
memset(f,0x3f,sizeof(f));
f[a[1][1]][1][1]=a[1][1]*a[1][1];
for(re int i=1;i<=n;i++){
for(re int j=1;j<=m;j++)
for(re int k=1;k<=1800;k++){
if(k<a[i][j]) continue;
f[k][i][j]=min(f[k][i][j],f[k-a[i][j]][i-1][j]+a[i][j]*a[i][j]);
f[k][i][j]=min(f[k][i][j],f[k-a[i][j]][i][j-1]+a[i][j]*a[i][j]);
}
}
for(re int k=1;k<=1800;k++){
if(f[k][n][m]>=inf) continue;
ans=min(ans,(n+m-1)*f[k][n][m]-k*k);
}
printf("%d
",ans);
}
return 0;
}
C：小奇的仓库(warehouse)
美妙的换根dp
设f[i][j]表示i到其他点，后4位状态为j的路径数
f[x][0]=1
f[x][(j+w)%16]+=f[y][j]
f[y][(j+w)%16]+=(f[x][j]-f[y][((j-w)%16+16)%16])
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#define MAXN 100005
#define int long long
using namespace std;
int n,m,ans=0;
int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0,w[MAXN<<1];
void add(int u,int v,int val){
cnt++,to[cnt]=v,w[cnt]=val,nxt[cnt]=pre[u],pre[u]=cnt;
}
int g[MAXN],f[MAXN][17],t[MAXN][17];
void DFS(int x,int fa){
f[x][0]=1;
for(int i=pre[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
DFS(y,x);
g[x]+=g[y];
for(int j=0;j<16;j++){
f[x][(j+w[i])&15]+=f[y][j];
g[x]+=f[y][j]*w[i];
}
}
}
void dfs(int x,int fa){
for(int i=pre[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
int size=0;
for(int j=0;j<16;j++){
t[y][(j+w[i])&15]+=f[x][j]-f[y][((j-w[i])&15+16)&15];
size+=f[y][j];
}
g[y]=g[x]+(n-size*2)*w[i];
for(int j=0;j<16;j++) f[y][j]+=t[y][j];
dfs(y,x);
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1,u,v,val;i<n;i++){
scanf("%lld%lld%lld",&u,&v,&val);
add(u,v,val),add(v,u,val);
}
DFS(1,0);
dfs(1,0);
for(int i=1;i<=n;i++){
for(int j=0;j<16;j++){
int k=j^m;
g[i]+=(k-j)*f[i][j];
}
printf("%lld
",g[i]-m);
}
return 0;
}