文章目录

2050 Programming Competition

1006 冰水挑战

相似题目推荐

洛谷P1156

dp[i][j] 代表前i个挑战，选择了j个，最大的体力值是多少

#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 1e3+10;

LL dp[maxn][maxn];// 代表现在到了第i个，完成了j个，体力的最大值
LL a[maxn],b[maxn],c[maxn];
int main(void)
{
    int T;cin>>T;
    while(T--){
        int n,C;cin>>n>>C;
        dp[0][0] = C;
        for(int i = 1;i <= n; ++i){
            scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
            for(int j = 0;j <= i; ++j){
                // dp[i][j] <- dp[i-1][j-1] + 选第i个
                // dp[i][j] <- dp[i-1][j] + 不选第i个
                dp[i][j] = 0;
                if(dp[i-1][j] > 0)
                    dp[i][j] = dp[i-1][j]+c[i];
                if(min(dp[i-1][j-1],b[i])> a[i]){
                    dp[i][j] = max(dp[i][j],min(dp[i-1][j-1],b[i])-a[i]+c[i]);
                }
            }
        }
        for(int i = n;i >= 0; --i)
            if(dp[n][i] > 0){
                printf("%d\n", i);
                break;
            }

    }

   return 0;
}

1005 球赛

dp[i][j][k] 代表已经打了i次比赛，比分为j:k 时的进行的局数最多是多少
这道题还有就是将状态压缩
例如10:10 和9:9 状态相同，这样j,k 的取值范围[0:10]
选择dp[i][j][k] 递推下面的状态是容易的，因为往下只有两个状态，而如果你知道j,k不太容易得知之前的状态


#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 1e4+10;
int dp[maxn][11][11];// dp[i][j][k] 代表进行了i次赛，当前比分是j:k,最多完成了多少局
// 状态转移; dp[i][j][k] 
// dp[i][j][k] = 转移，到i+1,
// A dp[i][j][k] 转移到 dp[i][j+1][k]
// B dp[i][j][k] 转移到 dp[i][j][k+1]
// ？ 都可以转移
// 
// 根据入度，出度选择我为人人还是人人为我型，判断哪一种更容易转移状态,我为人人需要提前将所有的状态初始化
char ar[maxn];
inline void chkmx(int &a,int b){
	a = a<b?b:a;
}
int main(void)
{
	int T;cin>>T;
	while(T--){
		scanf("%s",ar+1);
		int n = strlen(ar+1);
		memset(dp,-1,sizeof(dp));
		dp[0][0][0] = 0;
		for(int i = 0;i < n; ++i){
			for(int j = 0;j <= 10; ++j){
				for(int k = 0;k <= 10; ++k){
					if(dp[i][j][k] == -1) continue;
					if(ar[i+1] != 'B'){
						int  x = j+1;
						int  y = k;
						int  p = 0;
						if(x == 11) x = 0,y = 0,p = 1; 
						if(x == 10 && y == 10)
							x = 9,y = 9;
						chkmx(dp[i+1][x][y],dp[i][j][k]+p);
					}
					if(ar[i+1] != 'A'){
						int x = j;
						int y = k+1;
						int p = 0;
						if(y == 11) x = 0,y = 0,p = 1;
						if(x == 10&&y == 10)
							x = 9,y = 9;
						chkmx(dp[i+1][x][y],dp[i][j][k]+p);
					}
				}
			}
		}
		int ans = 0;
		for(int j = 0;j <= 10; ++j)
			for(int k = 0;k <= 10; ++k)
				ans = max(ans,dp[n][j][k]);
		printf("%d\n",ans);
	}
    

   return 0;
}