fjnu 2013校試合G
2008 ワード
タイトル:
n個の標的を与え、1本の線に並べ、各標的の得点は3種類あり、1、隣接する標的が打たれなければ、この標的の点数a[i].2、もし隣の標的が一つの標的を落としたら、この標的の点数b[i].3、隣の2つの標的が全部落ちたら、この標的の点数c[i];
問題:
この問題を線形に解決したdp[i][2][2]第1の状態:第iの標的、第2の状態:1は前の標的が0の反対に当たったことを示す.3番目の状態:1はこのターゲットが当たったことを示し、0はこのターゲットが当たっていないことを示します.
6つの状態遷移方程式.
n個の標的を与え、1本の線に並べ、各標的の得点は3種類あり、1、隣接する標的が打たれなければ、この標的の点数a[i].2、もし隣の標的が一つの標的を落としたら、この標的の点数b[i].3、隣の2つの標的が全部落ちたら、この標的の点数c[i];
問題:
この問題を線形に解決したdp[i][2][2]第1の状態:第iの標的、第2の状態:1は前の標的が0の反対に当たったことを示す.3番目の状態:1はこのターゲットが当たったことを示し、0はこのターゲットが当たっていないことを示します.
6つの状態遷移方程式.
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int oo=0x3f3f3f3f;
const ll OO=1LL<<61;
const ll MOD=10007;
const int maxn=100000+5;
int a[maxn],b[maxn],c[maxn];
int dp[maxn][2][2];
void become(int a,int t,int& b)
{
if(a==-1)return;
b=max(a+t,b);
}
int main()
{
int T,n;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %d %d",&a[i],&b[i],&c[i]);
memset(dp,-1,sizeof dp);
dp[0][0][0]=0;
dp[0][0][1]=0;
for(int i=0;i<n;i++)
{
become(dp[i][0][0],0,dp[i+1][0][0]);
become(dp[i][0][0],0,dp[i+1][0][1]);
become(dp[i][1][0],0,dp[i+1][0][0]);
become(dp[i][1][0],0,dp[i+1][0][1]);
become(dp[i][0][1],a[i+1],dp[i+1][1][0]);
become(dp[i][0][1],b[i+1],dp[i+1][1][1]);
become(dp[i][1][1],b[i+1],dp[i+1][1][0]);
become(dp[i][1][1],c[i+1],dp[i+1][1][1]);
}
int ans=max(dp[n][0][0],dp[n][1][0]);
printf("Case %d: %d
",cas,ans);
}
return 0;
}
/***
dp[i][0][0] -> dp[i+1][0][0];
dp[i][0][0] -> dp[i+1][0][1];
dp[i][0][1]+a[i] -> dp[i+1][1][0];
dp[i][0][1]+b[i] -> dp[i+1][1][1];
dp[i][1][0] -> dp[i+1][0][0];
dp[i][1][0] -> dp[i+1][0][1];
dp[i][1][1]+b[i] -> dp[i+1][1][0];
dp[i][1][1]+c[i] -> dp[i+1][1][1];
*/