#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;string s;while(n--){bool f1=0;bool f2=0;bool f=0;cin>>s;char ch=getchar();for(int i=0;i<s.length();i++){if(s[i]=='m'&&f1==0){f1=1;continue;}else if(s[i]=='q'&&f2==0&&f1==1){f1=0;continue;}else{f=1;break;}}if(f||f1)cout<<"No"<<endl;//注意最后判斷時，還要判斷f1，因為f1=0才說明mq都配對成功，沒有多余的melse cout<<"Yes"<<endl;}return 0;}
2. 三角形 dp問題 我們可以用dp來把所有的情況都算出來，最后取他要求的前m大就行 dp[i][j]表示前i個寶箱，裝的寶物價值為j的方案數量，dp=0則說明沒有這種情況 轉移方程： dp [ i ] [ k ] + = dp [ i - 1 ] [ k - a [ i ] [ j ] ] ; 最后把dp [ n ] [ j ] ( j = 1 ~ tot）加起來，不要忘了還有限制條件前k個 tot是寶物的最大價值（即每組最貴的寶物之和）
#include<bits/stdc++.h>
using namespace std;
const int maxn=10200;
int a[maxn][maxn];
int dp[maxn][maxn];
int sum=0;
int tot=0;
int main(){int n,k;int m[maxn];cin>>n>>k;dp[0][0]=1;memset(m,0,sizeof(m));for(int i=1;i<=n;i++){cin>>m[i];for(int j=1;j<=m[i];j++){cin>>a[i][j];sum=max(sum,a[i][j]);}tot+=sum;// cout<<tot<<endl;}sum=0;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m[i]; j ++)for(int k = tot; k >= a[i][j]; k --)dp[i][k] += dp[i - 1][k- a[i][j]];for(int i=1;i<=tot;i++){// cout<<dp[n][i]<<endl;if(k>=dp[n][i]){sum+=i*dp[n][i];k-=dp[n][i];}else{sum+=i*k;break;}}cout<<sum;return 0;}
3. 區間加 題解： 序列區間的問題可以考慮差分 先注意題目要求：每個區間的頭與尾都是不相同的，也就是說每個位置不能同時放多個左括號或右括號，但允許同時放 ( 和 ) 首先我們用a1[]來存a距離目標m差多少 a1 [ ] = m - a [ ] 然后用b來存a1的差分 b [ i ] = a [ i ] - a [ i - 1 ] 根據b的值分成四種情況： 1.當b<-1||b>1,此時i-1與i兩個位置的數，差值大于等于2。比如b=2，意味著i位置的數要比i-1位置的數多操作兩次，那就說明i-1與i之間要有兩個左括號才可以，這樣區間包括i但是不包括i-1，但題目要求一個位置不存在多個左括號，所以遇到這種情況，就說明此數據根本無法滿足題目要求，輸出0即可 2.如果b=1，說明i要比i-1多操作一次，那就是i-1與i之間有一個左括號，i-1 （ i，這樣i就在一個區間里而i-1不在，i就比i-1多操作一次。 光有左括號不行還要有右括號，我們可以先把右括號的位置待定，因為后面的數據還沒處理到，你不知道右括號要放哪，用w來表示還沒配對的左括號的數量。b=1時，w++ 3.b=-1時，就是上一種情況反過來，i-1與i之間有一個右括號，此時用到右括號，就去看之前有多少左括號，好去配對 sum用于記錄總值，初始為1 sum+=sumw 有w個左括號，說明此處可以形成w個區間，之前已經有sum個區間了，總區間數就是sumw 4.b=0,說明i-1與i相等，那他們倆就在同一個區間里。我們可以選擇不操作，如果在i之前有左括號，i之后可以放右括號 sum=sum*w+sum
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=998244355;
const int maxn=2010;
ll a[maxn],a1[maxn],b[maxn];
using namespace std;
int n,m;
ll sum=1,ant;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];a1[i]=m-a[i];b[i]=a1[i]-a1[i-1];}int w=0;for(int i=1;i<=n;i++){if(b[i]<-1||b[i]>1){cout<<0;return 0;}else if(b[i]==1)w++;else if(b[i]==-1){sum=(sum*w)%mod;w--;}else if(b[i]==0){sum=(sum*(w+1))%mod;}}cout<<sum;}
