今天比賽考的灰常不好，主要原因還是策略問題
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/263.html
標籤：C++
上一篇：C/C++編程筆記：開源中國最火的幾種開源專案，你值得擁有！
下一篇：c++中const的用法