今天比赛考的灰常不好,主要原因还是策略问题
T1 【NOIP2010TG】机器翻译
题目大意
给定N个数字,M个内存,将N不断查询,存入内存中,若内存中有了就不用查询,内存满后弹出第一个插入的,因此类推,问查询次数。
思路
㵘题,直接桶+离散化\(O(M)\)过了,还可以用循环队列来过,不过这样查询就成了\(O(M)\),复杂度略高,但此题数据范围极小,可以忽视.
注意,代码仅供参考
#include<bits/stdc++.h>
using namespace std;
int n,m,s,ans,head=1,cnt;
int a[10001],b[10001];
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
if(!a[t])
{
if(s <= m-1)
{
s++;
ans++;
a[t]=1;
b[++cnt]=t;
}
else
{
a[b[head]]=0;
head++;
ans++;
a[t]=1;
b[++cnt]=t;
}
}
}
printf("%d",ans);
return 0;
}
T2 【NOIP2010TG】乌龟棋
题目大意
给定N个格子,每个格子都有一个分值,有M张卡牌,每张卡牌都有一个数字,只可能是1,2,3,4,使用一张卡牌,就能移动相应的步数,保证卡牌用完后刚好到终点,问可以获得的最大分值。
思路
DP题。
考试时我看准了50分的思路,想pmx那样定义了一个五维数组\(F_{i,j,k,l,o}\),代表走到第i格时每种卡牌剩的张数,但没调出来。
正确思路其实跟50分的差不多,思考后,我们发现,i维是完全没有用的,有了卡牌剩余张数,其实就可以推出位置了,可以定义\(cal(i,j,k,l)\)求位置,转移方程就是\(F_{i,j,k,l}=max(F_{i+1,j,k,l}+a_{cal(i,j,k,l)},F_{i,j+1,k,l}+a_{cal(i,j,k,l)},F_{i,j,k+1,l}+a_{cal(i,j,k,l)},F_{i,j,k,l+1}+a_{cal(i,j,k,l)})\)
最后输出\(F_{0,0,0,0}\)就可以了。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1001],b[1001],dp[41][41][41][41],s[5];
int cal(int a,int b,int c,int d){ return 1+s[1]-a+(s[2]-b)*2+(s[3]-c)*3+(s[4]-d)*4; };
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&b[i]);
s[b[i]]++;
}
// dp[s[1]][s[2]][s[3]][s[4]]=a[1];
for(int i=s[1];i>=0;i--)
{
for(int j=s[2];j>=0;j--)
{
for(int k=s[3];k>=0;k--)
{
for(int l=s[4];l>=0;l--)
{
if(n-i >= 1)
{
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i+1][j][k][l]+a[cal(i,j,k,l)]);
}
if(n-i >= 2)
{
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j+1][k][l]+a[cal(i,j,k,l)]);
}
if(n-i >= 3)
{
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k+1][l]+a[cal(i,j,k,l)]);
}
if(n-i >= 4)
{
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k][l+1]+a[cal(i,j,k,l)]);
}
}
}
}
}
cout<<dp[0][0][0][0]<<endl;
return 0;
}