T1:

设DP[i][j]为第 i天选第j种方式的最少休息天数。

DP[0][0]=1,DP[0][1]=DP[0][2]=0;其余为INF

转移：有比赛和没比赛分类讨论，可以健身和不可健身分类讨论，再转移。

            dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
        if(a[i]==1){
            dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
        }
        if(a[i]==2){
            dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
        }
        if(a[i]==3){
        	dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
        	dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
		}

答案：min(dp[n][0],dp[n][1],dp[n][2])

T2:

题目：

给定一个正整数 m 和一个非负整数 s，你的任务是找出长度为 m各位数字之和为 s的最小和最大数。这些数应为非负整数，且十进制表示中不能有前导零。

思路：最大数高位尽可能高，最小数低位尽可能低。

做法： 若每一位都填9，都还有剩下的，则-1 -1.即m*9>s

 最大数：若当前剩余>=9,输出9.最后输出剩下的数字和0.
  
 最小数：正整数不能有前导0。所以最高位先填1，再从低位往高位填9，若余数在最高位，则最高位加上这个余数。

#include<bits/stdc++.h>
using namespace std;
int m,s;
int ans[1005];
int main(){
	cin>>m>>s;
	if(m*9<s||(s==0&&m>1)){
		cout<<-1<<" "<<-1;
        return 0;
	}
	int s_=s;
	int cnt=m;
	ans[1]=1;
	s-=1;
	while(s>=9){
		ans[cnt]+=9;
		cnt--;
		s-=9;
	}
	if(cnt!=1)
	ans[cnt]=s;
	else ans[cnt]+=s;
	s=s_;
	for(int i=1;i<=m;i++){
		cout<<ans[i];
	}
	cout<<" ";
	cnt=1;
	while(s>=9){
		cout<<9;
		s-=9;
		cnt++; 
	}
    if(cnt<=m)
	cout<<s;
	for(int i=cnt+1;i<=m;i++){
		cout<<0;
	}
	return 0;
}

T3:

分析：设dp[i]为i~n为合法时最少删除数量。

转移：删除当前位置：1 + dp[i+1]

保留：dp[i+a[i]+1]

初始状态：dp[n+1]设为0，dp[n~max(a[i])]=INF

#include<bits/stdc++.h>
using namespace std;
int t,n;
int a[200005];
int dp[4000005];
int main(){
	cin>>t;
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){scanf("%d",a+i);dp[i+a[i]+1]=0x3f3f3f3f;}
        dp[n+1]=0;
		for(int i=n;i>=1;i--){
			dp[i]=min(dp[i+1]+1,dp[i+a[i]+1]);
		}
		printf("%d\n",dp[1]);
	}
	return 0;
}

T4:

分析：设前i个字符的划分总数为dp[i]，最少要分出g[i]个。

 由题意，每段字符的最长长度由最小的a[s[i]]决定

做法：

固定终点i，向左枚举起点j，在这个过程中求最小长度,在这个长度满足条件(j~i就是一个合法子串)时更新划分总数dp[i]=dp[j-1]+dp[i]

和最长合法子串长，g[i]=min(g[i],g[j-1]+1)

初始化： g[1~n]=INF;dp[0]=1;f[0]=1;g[0]=0;

答案：g[n],最大长度，f[n].

T5:

题目：下一步有限制。先走不动的，就输了。 分析：对于每个点，由于双方都会做出最优选择，即双方都会走那个最近的合法点，一定走不出下一步的点一定是从数值大的点来的 所以从大到小遍历，对于每个点能走到的点，标记为反。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005],b[100005];
bool wins[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[a[i]]=i;
	}
	for(int i=n;i>=1;i--){
		int p=b[i];
		for(int j=p+a[p];j<=n;j+=a[p]){
			if(!wins[j]&&a[j]>a[p])wins[p]=true;
		}
		for(int j=p-a[p];j>=1;j-=a[p]){
			if(!wins[j]&&a[j]>a[p])wins[p]=true;
		}
	}
	for(int i=1;i<=n;i++){
		if(wins[i])cout<<"A";
		else cout<<"B";
	}
	return 0;
} 

T6: 数位dp。用DFS实现，三个参数：p记录到第几位了，l记录用了多少非0数，t记录与最高是否全部一致。 根据t确定本次枚举的最高值up,若t0则up=9,i从0到up，DFS更新。注意0要把l+1，仅iup且t==1时下一层DFS时t=1 若l>3 return 0，p<0 return 1.

#include<bits/stdc++.h>
using namespace std;
int t;
//p:第几位 l：当前用了多少非0数 y:是否与最高一致 
long long l,r;
vector<int>a;//分位存数 
long long ans[20][5];
long long dfs(int p,int l,int y){
	if(l>3)return 0;
	if(p<0)return 1;
	int up;
	if(y){
		up=a[p];
	} else {
		up=9;
	}
    if(!y&&ans[p][l]){
        return ans[p][l];
    }
    long long res=0;
	for(int i=0;i<=up;i++){    
        res+=dfs(p-1,l+(i!=0),y&&(i==up));
	}
    if(!y)ans[p][l]=res;
    return res;
}
long long count(long long x){
	int p=0,l=0,y=true; 
	long long xx=x;
	a.clear();
	while(xx){
		a.push_back(xx%10);
		xx/=10;
	}
    return dfs(a.size()-1,l,y);
} 
int main(){
cin>>t;
while(t--){
	cin>>l>>r;
	cout<<count(r)-count(l-1)<<"\n";
}
	return 0;
}